Algorithms and Data Structures

Bracket Sequences

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.

Examples

Input
Output
3
((())) (()()) (())() ()(()) ()()()

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 7 MB

To check your solution you need to sign in
Sign in to continue