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.