A valid bracket sequence is defined as follows: 1. The empty string is valid. 2. If string $S$ is valid, then $(S)$ is also valid. 3. If strings $A$ and $B$ are valid, then $AB$ is also valid.

You are given a string of length $N$ consisting of '(' and ')', with positions labeled from $1$ to $N$. There are four types of operations on this string:

1. Replace a b c: Change all brackets in the range $[a, b]$ to $c$. For example, if the original string is ))())())(, then executing Replace 2 7 ( changes the string to )(((((()(.
2. Swap a b: Reverse the substring in the range $[a, b]$. For example, if the original string is ))())())(, then executing Swap 3 5 changes the string to ))))(())(.
3. Invert a b: Change all '(' to ')' and all ')' to '(' in the range $[a, b]$. For example, if the original string is ))())())(, then executing Invert 4 8 changes the string to ))((()(((.
4. Query a b: Query the minimum number of changes required to make the substring in the range $[a, b]$ a valid bracket sequence. A change is defined as flipping a '(' to ')' or a ')' to '('. Note that the Query operation does not change the current bracket sequence. For example, if the original string is ))())())(, then the result of Query 3 6 is $2$, because one must change the ')' at position $5$ to '(' and the '(' at position $6$ to ')'.

Input

The first line contains two space-separated positive integers $N$ and $M$, representing the length of the string and the number of operations to be performed, respectively. The second line contains the initial string $S$ of length $N$. The following $M$ lines contain the $M$ operations to be performed in order, where the operation name and operands, as well as adjacent operands, are separated by spaces. $30\%$ of the data satisfies $N, M \le 3000$. $100\%$ of the data satisfies $N, M \le 100000$.

Output

The output contains $T$ lines, where $T$ is the number of Query operations in the input. Each Query operation corresponds to one line in the output, containing a single non-negative integer representing the result of the corresponding Query operation, i.e., the minimum number of changes required to make the specified substring a valid bracket sequence. The input data guarantees that a solution exists.

Examples

Input 1

4 5
((((
Replace 1 2 )
Query 1 2
Swap 2 3
Invert 3 4
Query 1 4

Output 1

1
2

Note

There are $2$ Query operations in the input, so there are $2$ lines of output. When the first Query operation is executed, the bracket sequence is ))((. Changing the $1$st position makes the substring in $[1, 2]$ a valid bracket sequence, so the first line of output is $1$. When the second Query operation is executed, the bracket sequence is )((), and changing the $1$st and $2$nd positions makes the substring in $[1, 4]$ a valid bracket sequence, so the second line of output is $2$.