Another Contest 1 Problem 1 - Binary String Operations

View as PDF

Submit solution


Points: 25
Time limit: 1.0s
Memory limit: 256M

Problem type

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

Comments

There are no comments at the moment.