问题描述

给定一个长度为 $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

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