Vacation Query

Source: AtCoder

Version: Phuoc Hung OJ Extended

Problem Statement

Maintain a binary string under range flips and queries for the longest consecutive run of ones in a range.

Input

The first line contains $N,Q$ and the second line a binary string $S$. Each query c L R is:

• 1 L R: flip bits on $[L,R]$.
• 2 L R: print the longest consecutive run of 1 inside $S_L\ldots S_R$.

Output

Print one line for every type 2 query.

Subtasks

• 20 points: $N,Q\le50$.
• 30 points: $N,Q\le5000$.
• 50 points: $N\le5\cdot10^5$, $Q\le10^5$.

Examples

Input

7 6
1101110
2 1 7
2 2 4
1 3 6
2 5 6
1 4 7
2 1 7

Output

3
1
0
7

Explanation

The first two answers are 3 and 1. Flipping $[3,6]$ gives 1110000, so $[5,6]$ has no ones. Flipping $[4,7]$ then gives 1111111, so the final answer is 7.