括号洗牌（Shuffle）

题目描述

乐柠兔有一个只包含左括号 ( 和右括号 ) 的字符串 $s$。

一个括号序列被称为合法括号序列，当且仅当它满足：

1. 整个序列中左括号数量等于右括号数量；
2. 任意前缀中左括号数量不少于右括号数量。

现在定义一种“括号洗牌”操作。

对于字符串 $s$ 中的每一个字符，计算它前面所有字符组成的前缀的括号平衡值。括号平衡值定义为：

也就是说，对于第 $i$ 个字符，需要记录三项信息：

1. 第 $i$ 个字符前面的前缀平衡值；
2. 字符的位置 $i$；
3. 字符本身。

接下来，将所有字符按照如下规则重新排序：

1. 前缀平衡值较小的字符排在前面；
2. 若前缀平衡值相同，则原位置较大的字符排在前面。

排序后，按照新的顺序依次取出字符，得到的新字符串就是 $s$ 的括号洗牌结果。

给定一个非空合法括号序列 $s$，请输出它的括号洗牌结果。

输入格式

输入一行一个字符串 $s$。

保证 $s$ 是一个非空合法括号序列。

输出格式

输出一行一个字符串，表示 $s$ 的括号洗牌结果。

样例

样例输入 #1

(()(()))

样例输出 #1

()(()())

样例解析

对每个字符记录“前缀平衡值、位置、字符”后，可以得到：

按照前缀平衡值从小到大排序，若相同则按位置从大到小排序，字符顺序变为：

( ) ( ( ) ( ) )

所以输出 ()(()())。

数据范围与约定

令$M = |s|$ ,对于 $100\%$ 的数据，保证：

• $2 \le |s| \le 5 \times 10^5$；
• $s$ 只包含字符 ( 和 )；
• $s$ 是合法括号序列。

特殊性质说明：

• A：$s$ 形如若干个 () 拼接而成；
• B：$s$ 形如若干个左括号后接相同数量的右括号。