题目描述

本题中「合法括号串」的定义如下：

1. 空串是「合法括号串」。
2. 若 $s$ 是「合法括号串」，则 $(s)$ 是「合法括号串」。
3. 若 $s,t$ 是「合法括号串」，则 $st$ 是「合法括号串」。

有一个括号串 $s$。$m$ 次询问：

• l r：求字符串 $t=s_ls_{l+1}\cdots s_r$ 的所有子序列中，长度最长的「合法括号串」，输出长度即可。

输入格式

第一行一个长度不超过 $10^6$ 的括号串 $s$。

第二行一个整数 $m$，$1\le m\le 10^5$。

接下来 $m$ 行，每行两个整数，表示一次询问。

输出格式

对于每次询问，在一行中输出一个整数表示答案。

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

0
0
2
10
4
6
6