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):

This is one of the optimal ways, thus the answer is ~2~.