Valid Parentheses String

Problem Description

Given a parentheses string $S$ of length $n$, there are $m$ queries. For each query, find the length of the longest subsequence within the interval $[l, r]$ that is a valid parentheses string.

A parentheses string is a string consisting only of ( and ).

A valid parentheses string is defined as follows:

1. The empty string is a valid parentheses string.
2. If $S$ is a valid parentheses string, then $(S)$ is a valid parentheses string.
3. If $S$ and $T$ are valid parentheses strings, then $ST$ is a valid parentheses string.

Input Format

The first line contains two integers $n, m$ as described ($1 \le n, m \le 10^5$).

The second line contains a string $S$, guaranteed to contain only ( and ).

The following $m$ lines each contain two integers $l, r$ as described ($1 \le l \le r \le n$).

Output Format

Output $m$ lines in total; the $i$-th line is the answer to the $i$-th query.

Sample Input

10 5
))()()()))
6 10
7 8
7 7
7 8
4 9

Sample Output

2
2
0
2
4