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.