問題文

長さ N の正しいカッコ列をすべて、辞書順に出力してください。

ただし、正しいカッコ列は次のように定義されています :

• () は正しいカッコ列である
• S が正しいカッコ列であるとき、文字列 ( +S+ ) は正しいカッコ列である
• S,T が正しいカッコ列であるとき、文字列 S+T は正しいカッコ列である
• それ以外の文字列はすべて、正しいカッコ列でない

例えば、

• ()()
• (()())(())
• ()()()()()()()()

は正しいカッコ列ですが、

• )(
• )))()(((
• ((((a))))

は正しいカッコ列ではありません。

また、 ( の方が ) よりも辞書順で早いものとします。

制約

• 1 \leq N \leq 20
• N は整数

入力例 1

2

出力例 1

()

長さ 2 の正しいカッコ列は () のみです。

入力例 2

3

出力例 2

※何も出力しない場合もあります。

入力例 3

4

出力例 3

(())
()()

入力例 4

10

出力例 4

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