Welcome to ZOJ Problem Sets Information Select Problem Runs Ranklist ZOJ Problem Set - 4051
Infinite Parenthesis Sequence

Time Limit: 3 Seconds      Memory Limit: 65536 KB

BaoBao has just found a sequence $A = a_0, a_1, \dots, a_{n-1}$ of length $n$ in his left pocket. Each element $a_i$ in this sequence is either a left parenthesis '(' or a right parenthesis ')'. As BaoBao dislikes short sequences, he decides to make the sequence infinitely long!

Let's denote $b_i$ as the element in the $i$-th position of the infinite parenthesis sequence $B$. As $B$ is an infinite sequence, $i$ can be positive, zero, or even negative! To derive $B$ from $A$, one can use the following equations: $$\begin{cases}b_i = a_i & \text{if } 0 \le i < n \\ b_i = b_{i-n} & \text{if } i \ge n \\ b_i = b_{i+n} & \text{if } i < 0 \end{cases}$$

As BaoBao is bored, he also crafts a generator to generate an infinite number of parenthesis sequences from sequence $B$! Denote $B^k$ ($k \ge 1$) as the $k$-th infinite sequence generated by the generator and $b^k_i$ as the element in the $i$-th position of sequence $B^k$. For completeness, we define $B^0 = B$. One can derive $B^k$ from $B^{k-1}$ using the following equations: $$\begin{cases} b^k_i = b^{k-1}_{i+1} & \text{if } b^{k-1}_i = \text{'('} \\ b^k_i = b^{k-1}_{i-1} & \text{if } b^{k-1}_i = \text{')'} \end{cases}$$

To obtain a deeper insight of the sequence, BaoBao would like to calculate the number of left parenthesis '(' in the continuous subsequence $b^k_l, b^k_{l+1}, b^k_{l+2}, \dots, b^k_{r-1}, b^k_r$ of $B^k$. Please write a program to help him calculate the answer.

Input

There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains a string $s$ ($1 \le |s| \le 10^5$, $s_i \in \{\text{'('}, \text{')'}\}$) indicating the sequence $A$. The $i$-th character $s_i$ in $s$ indicates the value of $a_{i-1}$.

The second line contains an integer $q$ ($1 \le q \le 10^5$), indicating the number of queries.

For the following $q$ lines, each line contains three integers $k$, $l$ and $r$ ($0 \le k \le 10^9$, $-10^9 \le l \le r \le 10^9$), indicating a query.

It's guaranteed that neither the sum of $|s|$ nor the sum of $q$ of all test cases will exceed $10^6$.

Output

For each query output one line containing one integer, indicating the number of left parenthesis '(' in the continuous subsequence $b^k_l, b^k_{l+1}, b^k_{l+2}, \dots, b^k_{r-1}, b^k_r$ of $B^k$.

Sample Input

3
(())
3
0 -3 2
1 -2 3
2 0 0
))()(
3
0 -3 4
2 1 3
3 -4 -1
))()(()(
4
1234 -5678 9012
123 -456 789
12 -34 56
1 -2 3


Sample Output

3
3
0
4
1
1
7345
623
45
3


Hint

In the following explanation, the value of $b^k_0$ is marked in red and bold.

For the first sample test case, we have $B^0 =$ ...(())(())(())..., $B^1 =$ ...()()()()()()... and $B^2 =$ ...)()()()()()(..., so the answer is 3, 3 and 0.

For the second sample test case, we have $B^0 =$ ...))()())()())()(..., $B^1 =$ ...())()())()())()..., $B^2 =$ ...)())()())()())(... and $B^3 =$ ...()())()())()())..., so the answer is 4, 1 and 1.

Author: WENG, Caizhi
Source: The 2018 ACM-ICPC Asia Qingdao Regional Contest, Online
Submit    Status