Sereja 有一个括号序列 s1, s2, ..., sn,或者换句话说,一个长度为 n 的字符串 s,由字符“(”和“)”组成。
Sereja 需要回答 m 个查询,每个查询由两个整数 li, ri (1 ≤ li ≤ ri ≤ n) 描述。第 i 个查询的答案是序列 sli, sli + 1, ..., sri 的最大正确括号子序列的长度。帮助 Sereja 回答所有问题。
您可以在注释中找到子序列和正确的括号序列的定义。
输入
第一行包含字符序列 s1, s2, ..., sn (1 ≤ n ≤ 106),不带任何空格。每个字符都是“(”或“)”。第二行包含整数 m (1 ≤ m ≤ 105) — 查询数。接下来的 m 行中的每一行都包含一对整数。第 i 行包含整数 li, ri (1 ≤ li ≤ ri ≤ n) — 第 i 个查询的描述。
输出
将每个问题的答案打印在一行上。按照输入的顺序打印答案。
示例
输入 #1
())(())(())( 7 1 1 2 3 1 2 1 12 8 12 5 11 2 10
输出 #1
0 0 2 10 4 6 6
注意
长度为 |x| 的子序列字符串 s = s1s2... s|s| (其中 |s| 是字符串 s 的长度)是字符串 x = sk1sk2... sk|x| (1 ≤ k1 < k2 < ... < k|x| ≤ |s|)。
正确的括号序列是通过在字符串的字符之间插入字符“1”和“+”可以将括号序列转换为正确的文法表达式。例如,括号序列“()()”、“(())”是正确的(结果表达式“(1)+(1)”、“((1+1)+1)”),而“)(”和“(”则不正确。
对于第三个查询,所需的序列将为“()”。
对于第四个查询,所需的序列将为 «()(())(())»。