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.