Valid Parentheses Combinations

Given an integer \(n\) representing the number of pairs of parentheses, generate all possible combinations of well-formed (i.e., valid) parentheses.

Each combination must be printed on a new line in lexicographical order. For example, when \(n = 3\), the valid combinations are:

((()))
(()())
(())()
()(())
()()()

Your task is to implement an algorithm that, given \(n\) as input, outputs all valid parentheses combinations (one per line) in lexicographical order.

inputFormat

The input consists of a single integer, \(n\) (\(1 \le n \le 10\)), which represents the number of pairs of parentheses.

Input is provided via standard input (stdin).

outputFormat

Output all valid combinations of parentheses, each combination on a separate line, sorted in lexicographical order. Output is written to standard output (stdout).

## sample

1

()

</p>