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

- It is an empty string.
- It has the form of , where is a balanced string.
- It has the form , where and 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 of the following two operations:

- Output the length of the longest balanced subsequence of the substring from index to inclusive.
- Flip the bracket located at index . (i.e. from
`(`

to`)`

and vice versa)

#### Constraints

##### Subtask 1 [30%]

##### Subtask 2 [70%]

No additional constraints.

#### Input Specification

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

The second line will contain a string of length , the initial sequence of brackets. The string will only contain `(`

and `)`

.

Each of the next lines will start with either or . If it starts with , two integers and will follow. If it starts with , one integer will follow.

#### Output Specification

For each type 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 query, the whole substring `(())`

is balanced.

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

For the third type query, the required subsequence `()(())`

goes from index to , then to .

For the fourth type query, the whole substring `()`

is balanced after the update.

For the fifth type query, the whole string `()()(())()`

is balanced after the second update.

## Comments