The setting of this problem is the same as Problem F. The differences from Problem F are underlined.

You are given a string $S$ of length $N$ consisting only of ( and ).

Answer $Q$ queries. In the $i$-th query, you are given integers $L_i$ and $R_i$. Solve the following problem:

Let $X$ be the substring of $S$ from the $L_i$-th character to the $R_i$-th character. Consider choosing a positive integer $k$ and then choosing a substring $Y$ of the string obtained by concatenating $k$ copies of $X$. Here, $Y$ must be a regular bracket sequence. $Y$ is allowed to be an empty string.

Determine whether there exists a maximum possible length for $Y$, and if it exists, find that maximum value.

Regular Bracket Sequence

A regular bracket sequence is a string that can be reduced to an empty string by repeatedly removing the contiguous substring () zero or more times.

Input

The input is given from Standard Input in the following format:

N Q
S
L_1 R_1
L_2 R_2
...
L_Q R_Q

• $N, Q, L_i, R_i$ are integers.
• $1 \le N \le 2 \times 10^5$
• $1 \le Q \le 2 \times 10^5$
• $S$ is a string of length $N$ consisting only of ( and ).
• $1 \le L_i \le R_i \le N$

Output

Print $Q$ lines. For the $i$-th line, print the maximum possible length of $Y$ for the $i$-th query if it exists, and -1 otherwise.

Example

Sample Input 1

4 3
()((
2 3
1 4
3 4

Sample Output 1

-1
2
0

Note

• In the first query, $X =$ )(. For any positive integer $k$, if we concatenate $k$ copies of $X$ and remove the first and last characters, we obtain a regular bracket sequence of length $2k - 2$. Therefore, there is no maximum possible length for $Y$, so you should print -1.
• In the second query, $X =$ ()((. It can be proven that the maximum possible length of $Y$ is $2$. Therefore, print 2.
• In the third query, $X =$ ((. The maximum possible length of $Y$ is $0$, so print 0. Note that $Y$ can be an empty string.