← 返回题目列表

Codeforces · 380/C

C. Sereja 和括号

中文机器翻译题面 查看原题

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)”),而“)(”和“(”则不正确。

对于第三个查询,所需的序列将为“()”。

对于第四个查询,所需的序列将为 «()(())(())»。