407420: GYM102787 E Sneetches and Speeches 2

Note: In this version of the problem, queries of type 3 will not appear.

The sneetches are back on the beaches, with the great Sylvester McMonkey McBean! The $$$i$$$th sneetch has $$$a_i$$$ stars on his belly ($$$0 \leq a_i \leq 1$$$). Just like normal, many [$$$l...r$$$] ranges of sneetches will go through Sylvesters xor-with-1-inator. Formally, after an operation, for all positions between $$$l$$$ and $$$r$$$ inclusive, the sneetch at that position will have a star on his belly after if and only if he didn't have a star on his belly immediately before walking through the machine. You need to know the largest continuous range of sneetches that all have the same type of belly at each step. Easy stuff, right?

But wait! There is a very important detail still unaddressed: we are on a beach! And the great orator Demosthenes practices his speeches on a beach. Demosthenes is giving an inspiring speech which may at times incite the following behavior, doing one of the three things $$$q$$$ times:

1. Do the usual operation: make the sneetches in positions $$$[l..r]$$$ go through the machine. $$$l \leq r$$$

2. Talk to sneetches $$$[l..r]$$$ and convince them to reverse their order. After moving, the sneetches are relabeled $$$1$$$ to $$$n$$$ from left to right.

3. Queries of type 3 do not appear in this version.

After each operation, Sylvester needs you to report the size of the largest continuous range of sneetches that have the same number of stars on their belly.

The first line will contain two integers: $$$n$$$ and $$$q$$$ representing the number of sneetches and the number of queries. $$$1 \leq n, q \leq 3*10^5$$$

The second line will contain a string of 0s and 1s of length $$$n$$$. The $$$i$$$th character represents the number of stars on the $$$i$$$th sneech's belly initially.

$$$q$$$ lines follow, each of the form $$$t$$$ $$$l$$$ $$$r$$$ where $$$t$$$ is 1, or 2 representing the query type as described in the statement, and $$$1 \leq l \leq r \leq n$$$.

Print $$$q$$$ lines, each with a single integer: the length of the longest run of sneetches with the same belly type after each query.

8 8
00000000
1 1 3
2 2 7
1 2 4
1 5 6
2 5 5
2 1 8
2 4 5
1 6 8

5
4
4
5
5
5
5
3

7 7
0111111
1 3 7
1 1 7
2 1 4
1 2 6
2 1 6
1 1 2
2 2 7

5
5
4
3
3
2
3

This problem was inspired by the problem Sneetches, originally written by Matt Fontaine. The original problem only had queries of type 1.