Bracket sequences

Positive integer $n(1\le n\le 10)$. is given. Print in alphabetical order all correct bracket sequences of length **2n**, assuming that the character '$($' comes before '$)$' in the alphabet.

A correct bracket sequence is either an empty string, or a string like $(S)$, where $S$ is a correct bracket sequence, or a string like $S_1{S}_2$, where $S_1$ and $S_2$ are correct bracket sequences.

Input

One integer $n(1\le n\le 10)$.

Output

Print in alphabetical order all correct bracket sequences of length $2n$, one sequence per line, without spaces.

Examples