A string of characters is called a bracket sequence if there exists only
the characters '(
' and ')
' in the string.
A bracket sequence ~X~ is called simple if either:
~X~ is "
()
",~X~ takes the form "
(
Y)
", where ~Y~ is a simple bracket sequence.
For example, the bracket sequences ()
, (())
and (((())))
are
simple, whereas ()()
, )(
, (())()
or (()())
are not.
Consider a bracket sequence ~S~. We can perform the following operation on string ~S~: erase any substring of ~S~ that is a simple bracket sequence, concatenating the rest. Let us denote the complexity of string ~S~ being the least number of operations needed to perform on string ~S~, such that the string does not contain any more substrings that are simple bracket sequences.
Given a bracket sequence ~P~ of length ~n~, and ~q~ queries, the ~i~-th query having the form ~(l_i, r_i)~. Your task is to calculate the complexity of ~P_{l_i \ldots r_i}~, that is the substring obtained by taking the characters of ~P~ from the ~l_i~-th to the ~r_i~-th position, inclusive.
A string ~a~ is a substring of a string ~b~ if ~a~ can be obtained from ~b~ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.
Input
The first line contains two integers ~n~ and ~q~ (~1 \le n \le 10^5~, ~1 \le q \le 10^5~), denoting the length of ~P~, and the number of queries, respectively.
The next line contains a single bracket sequence ~P~ of length ~n~.
The ~i~-th out of the next ~q~ lines contains two integers ~l_i~ and ~r_i~ (~1 \le l_i \le r_i \le n~), denoting the ~i~-th query.
Output
Output ~q~ lines, the ~i~-th line containing the complexity of ~P_{l_i \ldots r_i}~.
Scoring
Subtask 1 (~40~ points): ~n, q \le 1000~.
Subtask 2 (~60~ points): No additional constraints.
The total score for this problem is ~100~.
Sample Input 1
8 3
(()))(()
1 8
1 5
2 8
Sample Output 1
2
1
2
Notes
In the first query, the string that we need to answer is ~P_{1\ldots 8}~
or "(()))(()
". We can perform the following sequence of operations
(the strikethrough characters are those that we delete):
(()))(
~\rightarrow~ ()
~\rightarrow~ (()))()(
This is one of the optimal ways, thus the answer is ~2~.
Comments