Given a binary string, support the following two operations:
Update(i, l) - take the substring starting at index
i of length
l within the binary string and reverse it. The reverse of string
1000. Given the string
Update(1, 3) changes the string to
Query(i, l) - take the substring starting at index
i of length
l within the binary string, and compute the length of the longest substring that only contains 1's. In the event the substring does not contain the digit 1, the
Query should return 0.
~1 \le N, Q \le 10^5~
~0 \le i_q < N~
~1 \le l_q \le N~
~i_q + l_q \le N~
The first line of input contains two positive integers, ~N~ and ~Q~.
The next line contains a binary string of length ~N~.
The next ~Q~ lines each contain three integers, ~t_q~, ~i_q~, and ~l_q~. If ~t_q~ is equal to ~1~, then the next operation
to perform is
Update(i_q, l_q). Otherwise, ~t_q~ will be equal to ~2~, and the next operation to perform is
Query operation, output the answer on its own line. Output answers to
Query operations in the
order they're presented in the input.
In the event no
Query operations are requested, do not output anything.
4 3 0101 2 1 3 1 2 2 2 1 3