Up and down X57029

Assume a two-dimensional world. A fly is initially at position $(0, 0)$, and it will make $n$ unitary movements to the right, never going underground. At each step, it will either stay at the same height, go up one unit, or go down one unit. Generate all possible paths of the fly.

For instance, this is a possible path for $n = 11$:

To encode paths, use ‘u’ for going up, ‘d’ for going down, and ‘h’ for moving horizontally. The previous path is encoded “uududhdhuud”.

Input

Input consists of an $n$ between 1 and 11.

Output

Print all possible paths in alphabetical order.