括号序列是由字符“(”和“)”组成的字符串,例如“(()((”)。
平衡括号序列是插入数字和运算后可以成为有效数学表达式的括号序列,例如“(()(()))”。
括号序列的平衡定义为左括号“(”的数量减去右括号“)”的数量。例如,序列“(()((”)的余额为3。
平衡括号序列也可以定义为平衡为 0 的括号序列,使得其每个前缀都具有非负平衡。
我们定义平衡洗牌操作,它采用括号序列并返回括号序列,如下所示:首先,对于输入序列的每个字符,我们计算该字符之前的序列前缀的平衡性,并将其与输入序列中字符的位置一起写在表中,例如:
前缀余额01212321位置12345678字符(()(()))
然后,我们按前缀余额的升序对该表的列进行排序,并按位置的降序排列打破联系。在上面的例子中,我们得到:
前缀余额01112223位置18427536字符()(()())
该表的最后一行形成另一个括号序列,在本例中为“()(()())”。该序列称为对输入序列应用平衡洗牌操作的结果,或者简称为输入序列的平衡洗牌。
给您一个平衡的括号序列。打印其平衡随机播放。
输入
输入的唯一一行包含仅由字符“(”和“)”组成的字符串$$$s$$$。该字符串保证是一个非空的平衡括号序列,其长度不超过$$$500\,000$$$。
输出
打印括号序列 $$$t$$$ — $$$s$$$ 的平衡洗牌。
示例
输入 #1
(()(()))
输出 #1
()(()())