You are given a one-indexed string of brackets of length $N$. A string of brackets is considered "balanced" if it is classified in one of the three categories listed below:

1. It is an empty string.
2. It has the form of $(A)$, where $A$ is a balanced string.
3. It has the form $AB$, where $A$ and $B$ are both balanced strings.

For example, ()(()) is balanced, but )()(() is not. A subsequence of a string is a string obtained by deleting some (possibly zero) characters of the string. Please note that a subsequence does not have to be contiguous. You are to write a program that supports $Q$ of the following two operations:

1. Output the length of the longest balanced subsequence of the substring from index $L_i$ to $R_i$ inclusive.
2. Flip the bracket located at index $P_i$. (i.e. from ( to ) and vice versa)

Constraints

$1\le N,Q\le {10}^5$

$1\le L_i\le R_i\le N$

$1\le P_i\le N$

Subtask 1 [30%]

$1\le N,Q\le {10}^3$

Subtask 2 [70%]

No additional constraints.

Input Specification

The first line of input will contain two integers $N$ and $Q$, the length of the string and the number of operations.

The second line will contain a string of length $N$, the initial sequence of brackets. The string will only contain ( and ).

Each of the next $Q$ lines will start with either $1$ or $2$. If it starts with $1$, two integers $L_i$ and $R_i$ will follow. If it starts with $2$, one integer $P_i$ will follow.

Output Specification

For each type $1$ operation, print one line containing the length of the longest balanced subsequence.

Sample Input

10 7
()))(())((
1 5 8
1 3 6
1 1 10
2 10
1 9 10
2 3
1 1 10

Sample Output

4
0
6
2
10

Explanation

For the first type $1$ query, the whole substring (()) is balanced.

For the second type $1$ query, there exists no balanced subsequence with positive length.

For the third type $1$ query, the required subsequence ()(()) goes from index $1$ to $2$, then $5$ to $8$.

For the fourth type $1$ query, the whole substring () is balanced after the update.

For the fifth type $1$ query, the whole string ()()(())() is balanced after the second update.