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 0001 is 1000. Given the string 0001, Update(1, 3) changes the string to 0100.

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.

Constraints

~1 \le N, Q \le 10^5~

~0 \le i_q < N~

~1 \le l_q \le N~

~i_q + l_q \le N~

Input Specification

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(i_q, l_q).

Output Specification

For each 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.

Sample Input

4 3
0101
2 1 3
1 2 2
2 1 3

Sample Output

1
2