Lexicographic order

Input

The input file contains a natural number $n$, which does not exceed $10$.

Output

Output all valid bracket sequences of length $2n$ in lexicographical order, with each sequence on a new line.

Examples