Correct bracket sequences

Given a natural number n, output all valid bracket sequences composed of n opening parentheses and n closing parentheses, arranged in lexicographical order.

Input

The input consists of a single number, n, where n is less than 12.

Output

Print each valid sequence on a separate line, ensuring that each line ends with a newline character.

Examples