Generate Parentheses

Given an integer n, generate all possible combinations of n pairs of balanced parentheses. A combination is valid if each opening parenthesis '(' has a corresponding closing parenthesis ')', and they are well nested. The total length of each sequence is \(2n\).

For example, when \(n = 3\), the valid combinations are:

• ((()))
• ((()())) (Note: This form is not valid for \(n=3\); see below)
• ((()))
• (()()()) (See explanation below)

Note: The expected output should list the combinations in lexicographical order.

Mathematical formulation: For a given \(n\), find all strings of length \(2n\) consisting of '(' and ')' such that the string is valid. A valid string satisfies the conditions that at every prefix, the number of '(' is at least the number of ')', and overall the counts are equal.

inputFormat

The input consists of a single integer n (\(0 \le n \le 12\)), representing the number of pairs of parentheses.

The input is read from standard input (stdin).

outputFormat

Output all valid combinations of parentheses in lexicographical order, each on a separate line. If n is 0, output an empty string.

The output is written to standard output (stdout).

## sample

1

()