Given a positive integer n, generate all valid bracket sequences of size 2n and print them in lexicographical order.

The definition of a Valid Bracket Sequence is as follows:

An empty string is a valid bracket sequence.

If S is a valid bracket sequence, then (S) is also a valid bracket sequence.

If A and B are valid bracket sequences, then AB is also a valid bracket sequence.

Input

The input consists of a single integer n (1 β€ n β€ 11).

Output

Output all valid bracket sequences of size 2n, with each sequence printed on a separate line. The sequences should be printed in lexicographical order.