G. Drum Rehearsal
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a binary string $$$s$$$ of length $$$n$$$ and must process $$$q$$$ operations of the following types:

  • 1 l r: For every $$$i$$$ ($$$l \le i \le r$$$), replace $$$s_i$$$ with $$$1 - s_i$$$.
  • 2 l r: Delete a subsegment of $$$s_l s_{l+1} \ldots s_r$$$ (possibly empty or the entire interval). Among all possible choices, find the maximum absolute difference between the number of characters 1 and the number of characters 0 in the remaining string. The deletion applies only to this operation and does not affect subsequent queries.
Input

There is only one test case in each test file.

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n,q \le 2 \cdot 10^5$$$).

The second line contains a binary string $$$s$$$ of length $$$n$$$.

Each of the next $$$q$$$ lines contains three integers $$$t$$$, $$$l$$$, and $$$r$$$ ($$$t \in \{1,2\}$$$, $$$1 \le l \le r \le n$$$), describing an operation.

It is guaranteed that there is at least one operation of type 2.

Output

For each operation of type 2, print one integer — the maximum possible absolute difference between the number of characters 1 and the number of characters 0 in the remaining string.

Examples
Input
5 5
11010
2 1 5
1 2 4
2 1 5
2 2 4
2 3 3
Output
2
2
2
1
Input
4 3
0101
2 1 4
1 1 4
2 1 4
Output
1
1
Note

In the first example:

  • The first operation is a query, and the queried interval is 11010. Deleting the character at position $$$3$$$ leaves 1110 in the queried interval, which contains $$$2$$$ more characters 1 than characters 0.
  • The second operation inverts the characters at positions $$$2$$$ through $$$4$$$, so the string becomes 10100.
  • The third operation is a query, and the queried interval is 10100. Deleting the character at position $$$1$$$ leaves 0100 in the queried interval, which contains $$$2$$$ more characters 0 than characters 1.
  • The fourth operation is a query, and the queried interval is 010. Deleting the character at position $$$2$$$ of this interval leaves 00 in the queried interval, which contains $$$2$$$ more characters 0 than characters 1.
  • The fifth operation is a query, and the queried interval is 1. Deleting the empty string leaves 1 in the queried interval, which contains $$$1$$$ more character 1 than characters 0.