
ZOJ Problem Set  4051
BaoBao has just found a sequence $A = a_0, a_1, \dots, a_{n1}$ 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_{in} & \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^{k1}$ using the following equations: $$\begin{cases} b^k_i = b^{k1}_{i+1} & \text{if } b^{k1}_i = \text{'('} \\ b^k_i = b^{k1}_{i1} & \text{if } b^{k1}_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_{r1}, b^k_r$ of $B^k$. Please write a program to help him calculate the answer. InputThere 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_{i1}$. 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$. OutputFor 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_{r1}, b^k_r$ of $B^k$. Sample Input3 (()) 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 Output3 3 0 4 1 1 7345 623 45 3 HintIn 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 ACMICPC Asia Qingdao Regional Contest, Online 