ブラケットシーケンス

正の整数 n が与えられたとき、長さが 2n のすべての正しい括弧列を生成し、辞書順(lexicographical order)に出力します。

正しい括弧列の定義は以下の通りです:

• 空文字列は正しい括弧列とみなします。

• S が正しい括弧列である場合、(S) も正しい括弧列です。

• A と B が正しい括弧列である場合、AB も正しい括弧列となります。

入力

入力は、1 つの整数 n (1 ≤ n ≤ 11) から構成されます。

出力

すべての長さが 2n の正しい括弧列を、辞書順に各行に 1 つずつ出力してください。

例