Generate Parentheses

Given an integer n, generate all combinations of well-formed parentheses containing n pairs. A valid combination must satisfy:

• The resulting string has a length of 2n.
• It contains exactly n '(' characters and n ')' characters.
• For any prefix of the string, the number of '(' is greater than or equal to the number of ')'.

In mathematical notation, if we denote the string by S of length L = 2n, then for every index 1 ≤ k ≤ L, if f(k) is the number of '(' in the prefix S[1..k] and g(k) is the number of ')' in the same prefix, the following condition must hold:

\(f(k) \ge g(k)\) and \(f(L)=g(L)=n\).

Your task is to print all valid combinations, one per line. The order of the output combinations should follow the natural order generated by the backtracking method.

inputFormat

The input consists of a single integer n (0 ≤ n ≤ 10) on a single line, representing the number of pairs of parentheses.

outputFormat

Output all valid combinations of well-formed parentheses. Each combination should be printed on a separate line. If n = 0, output a single empty line.

## sample

1

()

</p>