配点: 1000 点
問題文
的对应匹配括号序列 S 。
S 中第几个字符与第几个字符对应。
例如,
“(())() ,“
表示查询“Add1 信和
将其重写为 4 文字目」、「2 信和
将其重写为 3 文字目」、「5 信和
将其重写为 6 字符”是对应的。
在这里,对应的括号序列是符合以下任一条件的非空字符串。
()- 的对应匹配括号序列 A 存在并且
满足
(, A,)的字符串 - 的对应匹配括号序列 A,B 存在并且 满足A,B 的字符串
入力
输入是按以下格式从标准输入给出的。
S
出力
|S| 该值应乘以 S 的长度时,括号的对应关系按照以下形式表示 |S|/2 行。
l_1 r_1
:
l_{|S|/2} r_{|S|/2}
这是表示“l_1 信和 将其重写为 r_1 文字目」, ... ,「l_{|S|/2} 信和 将其重写为 r_{|S|/2} 第几个字符”与之对应。
输出需要满足以下条件。
- 1 \leq l_i < r_i \leq |S| \ (1 \leq i \leq |S|/2)
- \text{max}(l_i, r_i) < \text{max}(l_{i + 1}, r_{i + 1}) \ (1 \leq i \leq |S|/2 - 1)
制約
- 1 \leq |S| \leq 200,000
- S 是
您也可以写
()由字符组成的匹配括号序列
入力例 1
(())()
出力例 1
2 3 1 4 5 6