题目描述

给你一个长度为 $N$ 的字符串 $S$ ，它由 ( 和 ) 组成。您的任务是在 $S$ 中插入一定数量的 (和)，以得到一个_正确的括号序列_。 这里，正确括号序列的定义如下：

• () 是一个正确的括号序列。
• 如果 $X$ 是一个正确的括号序列，(X) 也是一个正确的括号序列。
• 如果 $X$ 和 $Y$ 是正确的括号序列，那么 XY 也是正确的括号序列。
• 每个正确的括号序列都可以根据上述规则推导出来。

添加的方案可能有多种，你需要找到字典序最小的情况，这样答案就唯一了。

注：ASCII 码中，( 小于 )。

输入格式

输入一个字符串 $S$，保证只有 ( 和 )

输出格式

输出一个字符串，为添加后的合法字符串。

3
())

(())

6
)))())

(((()))())

8
))))((((

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

提示

• $S$ 的长度为 $N$ 。
• $1 ≤ N ≤ 100$
• $S$ 仅由 ( 和 ) 组成。