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