G. The Meaning of the World
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

The meaning of the world must lie outside the world All things in the world are as they are and happen as they happen There is no value in the world —— Tractatus Logico-Philosophicus

Fengmi gives you a string $$$s$$$ of length $$$n$$$, consisting only of '(' and ')'.

You need to support $$$q$$$ operations:

  1. Flip the $$$k$$$-th bracket, i.e., change '(' to ')' and ')' to '('.
  2. Query the length of the longest valid parentheses substring in the interval $$$[l,r]$$$.
Formally, you need to compute:

$$$$$$f(l,r) = \max (\left\{ j - i + 1 \mid l \le i \le j \le r \land \text{valid}(i,j) \right\}\cup \{0\})$$$$$$

where $$$\text{valid}(i,j)$$$ indicates that the substring $$$s[i..j]$$$ is a valid parentheses sequence.

In this problem, a valid parentheses sequence is defined as follows:

  1. The empty sequence is a valid sequence.
  2. If $$$A$$$ is a valid sequence, then ($$$A$$$) is also a valid sequence.
  3. If $$$A$$$ and $$$B$$$ are both valid sequences, then $$$AB$$$ is also a valid sequence.
Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 2 \times 10^5$$$) — the length of the bracket string and the number of operations.

The second line contains a string $$$s$$$ of length $$$n$$$, consisting only of the characters '(' and ')'. The given string is not guaranteed to be a valid parentheses sequence.

The next $$$q$$$ lines each describe one of the following two operations:

  • 1 k ($$$1 \le k \le n$$$): flip the $$$k$$$-th bracket.
  • 2 l r ($$$1 \le l \le r \le n$$$): query the length of the longest valid parentheses substring in the interval $$$[l,r]$$$.
Output

For each operation of type $$$2$$$, output a single integer on its own line — the answer.

Examples
Input
8 5
()(()())
2 1 8
1 4
2 1 8
1 7
2 1 8
Output
8
4
4
Input
12 6
(()())(()())
2 1 12
1 3
2 1 12
1 8
2 1 12
2 4 9
Output
12
10
12
2
Note

Sample 1:

  • Initial string: ()(()()).
  • First query on interval $$$[1,8]$$$: the longest valid parentheses substring is ()(()()) (positions $$$1-8$$$), length $$$8$$$.
  • Flip the $$$4$$$th bracket: ()())()).
  • Second query on interval $$$[1,8]$$$: the longest valid parentheses substring is ()() (positions $$$1-4$$$), length $$$4$$$.
  • Flip the $$$7$$$th bracket: ()())(().
  • Third query on interval $$$[1,8]$$$: the longest valid parentheses substring is ()() (positions $$$1-4$$$), length $$$4$$$.

Sample 2:

  • Initial string: (()())(()()).
  • First query on interval $$$[1,12]$$$: the longest valid parentheses substring is the entire string, length $$$12$$$.
  • Flip the $$$3$$$rd bracket: (((())(()()).
  • Second query on interval $$$[1,12]$$$: the longest valid parentheses substring is (())(()()) (positions $$$3-12$$$), length $$$10$$$.
  • Flip the $$$8$$$th bracket: (((())())()).
  • Third query on interval $$$[1,12]$$$: the longest valid parentheses substring is (((())())()) (positions $$$1-12$$$), length $$$12$$$.
  • Fourth query on interval $$$[4,9]$$$: the longest valid parentheses substring is () (positions $$$4-5$$$), length $$$2$$$.