Online Longest Valid Parentheses

Given a sequence of parentheses represented by a binary sequence ( c_1,c_2,\cdots,c_n ) where ( c_i=0 ) represents a left bracket ( and ( c_i=1 ) represents a right bracket ), process ( q ) online operations.

There are two types of operations:

1. Query Operation: 1 l r
   For any subinterval ( [l',r'] ) within ( [l,r] ), define ( f(l',r')=1 ) if the bracket sequence ( c_{l'},c_{l'+1},\dots,c_{r'} ) forms a valid parentheses sequence and ( f(l',r')=0 ) otherwise. The query asks for ( \max_{[l',r']\subseteq[l,r]} { (r'-l'+1) \cdot f(l',r') } ), i.e. the length of the longest valid parentheses substring within ( [l,r] ).
   
   
2. Update Operation: 2 l r
   For every ( i ) in ( [l,r] ), update ( c_i ) to ( 1-c_i ), which flips the corresponding bracket (from ( to ) and vice versa).
   
   A valid parentheses sequence is defined as follows:
   

• The empty string is valid;
  
• If ( A ) is valid, then ( (A) ) is valid;
  
• If ( A ) and ( B ) are valid, then their concatenation ( AB ) is valid.

inputFormat

The first line contains two integers ( n ) and ( q ).
The second line contains a string of length ( n ) consisting of the characters '0' and '1'.
Each of the following ( q ) lines contains an operation in one of the following formats:

• 1 l r for a query operation.
  
• 2 l r for an update operation.
  It is guaranteed that ( 1 \le l \le r \le n ).

outputFormat

For each query operation (type 1), output the length of the longest valid parentheses substring within the specified range on a new line.

sample

4 3
0011
1 1 4
2 2 3
1 1 4

4
4