Generate Parentheses

Medium#recursion #backtracking· solved by 0 · time limit 2.0 s

Print all balanced strings of $n$ pairs of parentheses, in lexicographic order (( comes before )).

Input

A single integer $n$ .

One string per line.

$1 \le n \le 8$

Input

Output

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

Input

Output

()