Generate Valid Parentheses

Given an integer \( n \), generate all combinations of well-formed parentheses consisting of \( 2n \) characters. A valid parentheses string is defined as one where every opening parenthesis '(' has a corresponding closing parenthesis ')' and the pair of parentheses are properly nested.

Constraints:

• \( 1 \leq n \leq 12 \)

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

\[ ((())) ,\quad (()()) ,\quad (())() ,\quad ()(()),\quad ()()() \]

inputFormat

The input consists of a single integer \( n \) given on one line from standard input.

outputFormat

Output all valid parentheses combinations, each on a separate line, in lexicographical order.

## sample

1

()