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

3

5
((()))
(()())
(())()
()(())
()()()

1

1
()