4194 - STL 栈:括号匹配

通过次数

95

提交次数

131

Time Limit : 1 秒
Memory Limit : 128 MB

给定一个只包含左右括号的合法括号序列,按右括号从左到由的顺序输出每一对配对的括号的位置(括号序列以0开始编号)。

Input

输入格式:仅一行,表示一个合法的括号序列

Output

输出格式:设括号序列有n个右括号,则输出包括n行,每行两个整数l,r, 表示配对的括号左括号出现在第l位,右括号出现在第r位

Examples

Input

(())()

Output

1 2
0 3
4 5