Forbidden words P89318

Write a program that, given a number $n$, prints all the words that are a permutation of the first $n$ lowercase letters, with one restriction: there cannot be two letters $x$ and $y$ such that $y$ is immediately to the right of $x$ in the word and $y$ is the letter following $x$ in the alphabet.

Input

Input consists of a natural number $n$ between 1 and 9.

Output

Print in order and one per line all the words that satisfy the restriction.