题目描述

小怪的体力消耗的差不多了，胡图图又安排了智力游戏——添添乐。

• () 是匹配的括号序列。
• 如果 X 是匹配的括号列，(X) 是匹配的括号序列。
• 如果 X 和 Y 是匹配的括号序列，XY是匹配的括号序列。
• 所有其他括号序列都是不匹配的。

游戏给一定个长度为 $N$ 的由 ( 与 ) 组成的字符串序列 $S$, 请在合适的位置添加 ( 或 ) 让 $S$ 变成匹配的括号序列，输出添加数量最少的方案，如果有多种可能，请输出字典序排列最小的一种。

输入格式

第一行一个整数 $N$。

第二行一个字符串 $S$。

输出格式

一个字符串，把 $S$ 添加字符后字典序最小的匹配括号序列。

输入输出样例

3
())

(())

6
)))())

(((()))())

8
))))((((

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

数据规模与约定

对于 $100\%$ 的数据:

• $1 \le N \le 100000$。

• 子任务 1（$30$ 分）：$1 \le N \le 5$。

• 子任务 2（$30$ 分）：$1 \le N \le 100$。

• 子任务 3（$40$ 分）：没有特殊限制。