括号

给定一个整数 n。生成所有长度为 n 的合法括号序列，并按字典序升序输出。合法括号序列定义：

（1）空字符串是合法的；

（2）若字符串 s 合法，则 (+s+) 合法；

（3）若字符串 s 和 t 合法，则 s+t 合法。

时间限制：1000ms内存限制：256MB

输入格式

输入一个整数n。

输出格式

每行输出一个合法括号序列（按字典序升序）。若无解则不输出。

输入样例#1

2

输出样例#1

()

输入样例#2

4

输出样例#2

(())
()()

输入样例#3

6

输出样例#3

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

数据范围：

1≤N≤20，N 是偶数。