← 返回题目列表

Codeforces · 524/F

F. 还有另一个括号序列

中文机器翻译题面 查看原题

Polycarpus 具有有限的开括号和闭括号序列。为了不在讲座中睡着,波利卡普斯正在享受他的序列。他能够执行两种操作:

- 在任意位置添加任意括号(在开头、结尾或任意两个现有括号之间);
- 循环移位 - 将最后一个括号从序列末尾移动到开头。

Polycarpus 可以对其序列应用任意数量的操作,并以任意顺序添加循环移位。因此,他想要得到尽可能最小长度的正确括号序列。如果有多个这样的序列,Polycarpus 会对字典顺序上最小的一个感兴趣。帮他找到这样的序列。

正确的括号序列是左括号和右括号的序列,通过添加字符“1”和“+”可以得到正确的算术表达式。每个左括号必须对应于一个右括号。例如,序列“(())()”、“()”、“(()(()))”是正确的,而“)(”、“(()”和“(()))(”则不正确。

序列 a1 a2... an 按字典顺序小于序列 b1 b2... bn,如果从 1 到 n 存在这样的数字 i,则 1 ≤ k < i 且 ai < bi,那么ak = bk。考虑“(”<“)”。

输入

第一行包含由字符“(”和“)”组成的Polycarpus序列。线的长度为 1 到 1 000 000。

输出

打印Polycarpus通过其操作可以获得的最小长度的正确括号序列。如果有多个这样的序列,则打印字典顺序最小的一个。

示例

输入 #1

()(())

输出 #1

(())()

输入 #2

()(

输出 #2

(())

注意

第一个示例中的序列已经正确,但要获得字典顺序最小的答案,需要执行四次循环移位操作。在第二个示例中,您需要在第二个和第三个括号之间添加右括号并进行循环移位。您可以先进行移位,然后在末尾添加括号。