Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example 1:

Input: 1
Output:
()

Example 2:

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

Constraints:

• 1 ≤ n ≤ 8

Input format: A single integer n.

Output format: All valid combinations, one per line, in lexicographic order.