P16154 [ICPC 2016 NAIPC] Alternative Bracket Notation

平衡的括号序列是指每个左括号都能在字符串的后面找到一个与之匹配的右括号的序列。 :::align{center}  ::: 注意，每个右括号都与最近的一个未匹配的左括号相匹配。 定义一种新的括号表示法如下：每个括号对对应于一个形如“start,end:”的头部，其中 start 和 end 是新字符串本身的索引！索引 start 是紧跟在 ':' 之后的字符的索引，而 end 是最后一个包含在此括号对内的括号对所对应的头部的下一个索引。取新表示法的子串 substring(start, end)，你将得到一个替代的括号序列，它描述了与“start,end:”对应的括号对中包含的所有括号对！由于空括号对内部没有内容，其头部中的 start 和 end 相同。 每个索引在字符串中占用的字符数与其十进制表示的长度相同。（例如，索引 $42$ 将占用 $2$ 个字符）。新字符串中的索引从 $0$ 开始。在替代括号表示法字符串中找到的所有索引都是从新字符串开头算起的绝对索引。 考虑这个括号语句：$(())$ 这是它的新替代括号表示法：$4,8:8,8:$ 在这个例子中，有两组匹配的括号：外括号和内括号。外括号出现在内括号之前，因为起始括号先出现。因此，外括号的头部会出现在内括号的头部之前。头部 $4,8:$ 表示外括号，而头部 $8,8:$ 表示内括号。从第 4 个字符到第 7 个字符的子串是 $8,8:$，它表示外括号内部包含的内容。注意，$5,11:11,11:$ 也可能是合法的替代表示法，但我们希望得到最短的表示法，这就是为什么 $4,8:8,8:$ 是正确的答案。 :::align{center}  :::

每个输入包含单个测试用例。请注意，你的程序可能会在不同输入上多次运行。输入仅包含一行，其中包含一个字符串 $s$，该字符串仅由左括号和右括号组成。字符串 $s$ 的长度在 $2$ 到 $4{,}000$ 之间。没有空格。保证字符串 $s$ 是平衡的。

用新的替代括号表示法输出字符串 $s$。如果存在多种表示 $s$ 的方式，请选择最短的表示法，该表示法是唯一的。

翻译由 DeepSeek V3.2 完成