问题描述

给您一个长度为 $N$ 的字符串 $S$ ，由 ( 和 ) 组成。

您的任务是将一些 ( 和 ) 插入到 $S$ 中，以获得 正确 的括号序列。

这里，正确的括号序列定义如下：

• $()$ 是正确的括号序列。
• 如果 $X$ 是正确的括号序列，则 $(X)$ 也是正确的括号序列。
• 如果 $X$ 和 $Y$ 是正确的括号序列，$X$ 和 $Y$ 按此顺序连接也是正确的括号序列。
• 每个正确的括号序列都可以从上述规则中导出。

找出可以获得的最短正确括号序列。

如果有多个这样的序列，则找出字典序最小的一个。

输入格式

一个整数 $N(1≤N≤100)$ 和 一个字符串 $S$，$S$ 的长度为 $N$。

$S$ 由 ( 和 ) 组成。

输出格式

输出最短正确括号序列中字典顺序最小的字符串，该序列可以通过在 $S$ 中插入一定数量的 ( 和 ) 来获得。

3
())

(())

6
)))())

(((()))())

8
))))((((

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