Parentheses

Who doesn’t love parentheses?

Sashka stumbled upon a bracket sequence $S = s_1 s_2 \dots s_{2N}$ of $2N$ parentheses, from which $N$ are opening parentheses and $N$ are closing parentheses. She defines the bracket sequence’s clumsiness as the minimum number of required swaps of elements to turn it into a regular parentheses sequence. The regular parentheses sequences follow these rules:

• The empty sequence is a regular parentheses sequence.
• $S$ is a regular non-empty parentheses sequence iff two regular sequences $A$ and $B$ exist such that $S = \text{( + } A \text{ + ) + } B$, where $\text{+}$ denotes the operation concatenation of two sequences.

Task

Sashka wants to know the clumsiness for $Q$ such sequences $T_1, T_2, \dots, T_Q$, where the $i$-th of them $T_i = s_{L_i} s_{L_{i+1}} \dots s_{R_i}$ consists of all the elements in $S$ from position $L_i$ to $R_i$ inclusive. It is guaranteed that every sequence $T_i$ consists of equal number of opening and closing parentheses. Write a program which answers the $Q$ questions.

Input data

The first line of the standard input contains the three integers $N$, $Q$ and $G$, which describe the number of opening parentheses in the sequence, the number of questions and the number of the subtask that the test is from. The second line contains $2N$ parentheses, $s_1$, $s_2$, $\dots$, $s_{2N}$ respectively. The last $Q$ lines of the standard input contain the integers $L_i$ and $R_i$, which describe the positions for the $i$-th question.

Output data

On the standard output print one number on each line, the $i$-th number being the minimum number of required swaps to turn $T_i$ into a regular parentheses sequence.

Constraints and clarifications

• $1 \leq N, Q \leq 2 \cdot 10^5$
• $1 \leq L_i < R_i \leq 2N$
• All questions are different from one another.

• Only in the sixth subtask, one test is considered to be successfully passed by your solution, if you have found correctly all answers that are $0$. For the other questions in the test (for which the correct answers is not $0$), it is only needed that the printed number is a integer in the interval $[1, 10^{18}]$.

Example 1

stdin

3 1 1
)())((
1 6

stdout

1

Explanation

)())(( $\rightarrow$ (())()

Example 2

stdin

5 10 1
()))(()(()
2 9
6 7
1 10
3 8
7 10
3 10
9 10
4 7
4 5
3 6

stdout

2
0
1
1
1
1
0
1
1
1