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=(+A+)+B$, where $+$ denotes the operation concatenation of two sequences.

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 parentheses, which answers the $Q$ questions.

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.

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.

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