C. Sereja 与括号序列

每次测试的时间限制：$1$ 秒
内存限制：$256$ 兆字节

Sereja 有一个括号序列 $s_1, s_2, \dots, s_n$，换句话说，一个长度为 $n$ 的字符串 $s$，由字符 "(" 和 ")" 组成。

Sereja 需要回答 $m$ 个查询，每个查询由两个整数 $l_i, r_i$ 描述（$1 \le l_i \le r_i \le n$）。第 $i$ 个查询的答案是序列 $s_{l_i}, s_{l_i+1}, \dots, s_{r_i}$ 的 最长正确括号子序列 的长度。请帮助 Sereja 回答所有查询。

有关子序列和正确括号序列的定义，请参见提示。

输入

第一行包含一个字符序列 $s_1, s_2, \dots, s_n$（$1 \le n \le 10^6$），没有空格。每个字符是 "(" 或 ")"。
第二行包含整数 $m$（$1 \le m \le 10^5$）——查询的数量。
接下来的 $m$ 行，每行包含一对整数。第 $i$ 行包含整数 $l_i, r_i$（$1 \le l_i \le r_i \le n$）——第 $i$ 个查询的描述。

输出

对每个查询，在一行中输出答案。按照输入中的顺序输出答案。

示例

输入：

())(())(())(
7
1 1
2 3
1 2
1 12
8 12
5 11
2 10

输出：

0
0
2
10
4
6
6

提示

• 字符串 $s = s_1 s_2 \dots s_{|s|}$（其中 $|s|$ 是字符串长度）的一个长度为 $|x|$ 的子序列是字符串 $x = s_{k_1} s_{k_2} \dots s_{k_{|x|}}$（$1 \le k_1 < k_2 < \dots < k_{|x|} \le |s|$）。
• 正确括号序列是一个可以通过在字符串字符之间插入数字 $1$ 和运算符 $+$ 转换为正确算术表达式的括号序列。例如，括号序列 "()()"、"(())" 是正确的（得到的表达式是 "(1)+(1)"、"((1+1)+1)"），而 ")(" 和 "(" 是不正确的。

对于第三个查询，所需的序列是 "()"。
对于第四个查询，所需的序列是 "()(())(())"。