给定长度为 $N$ 的圆括号序列 $S$。只允许在 $S$ 的最前面或最后面添加若干个括号，使最终序列成为合法括号序列。小泽希望添加的括号总数尽可能少。请输出任意一个满足条件的最短结果。

输入格式

第一行输入 $N$，第二行输入长度为 $N$ 的括号串 $S$。

输出格式

输出在两端添加最少括号后得到的合法序列。

2
((

(())

9
))((()())

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

7
))())))

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

数据范围与约定

• $1\le N\le100$
• $S$ 只含 ( 和 )