A parenthesis string is balanced if every ( has a matching ) that closes it and no prefix has more ) than (. Given an integer n, output every balanced string that uses exactly n pairs of parentheses (so each string has length 2n).
To make the answer unique, print the strings in lexicographic order. Compare characters by ASCII, where ( (code 40) is smaller than ) (code 41).
Input format
A single line containing the integer n.
Output format
Line 1: an integer M, the number of balanced strings (the n-th Catalan number).
The next M lines: one balanced string per line, in lexicographic order. When n = 0 the only balanced string is the empty string, printed as an empty line.
Constraints
- 0 ≤ n ≤ 11