配点 : $400$ 点

問題文

( と ) で構成される $N$ 文字の文字列 $S$ が与えられる。$S$ にいくつかの ( または ) を挿入することで正しい括弧列を作りたい。
ただし、正しい括弧列は次のように定義されている：

• () は正しい括弧列である。
• $X$ が正しい括弧列であるとき、(、$X$、) をこの順につなげたものは正しい括弧列である。
• $X$、$Y$ が正しい括弧列であるとき、$X$ と $Y$ をこの順につなげたものは正しい括弧列である。
• それ以外の括弧列は正しくない。

そのとき、作れる最も文字数が少ない正しい括弧列を求めなさい。このようなものが複数ある場合は、辞書順最小のものを求めなさい。

制約

• $S$ の長さは $N$ である。
• $1 ≤ N ≤ 100$
• $S$ は ( と ) のみで構成されている。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $S$

出力

$S$ から (、) を挿入していったときに作れる最小の長さの正しい括弧列のなかで辞書順最小の文字列を出力しなさい。

入力例 1

3
())

出力例 1

(())

入力例 2

6
)))())

出力例 2

(((()))())

入力例 3

8
))))((((

出力例 3

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