Description

lxhgww recently received a $01$ sequence containing $n$ numbers, indexed from $0$. Each number is either $0$ or $1$. There are five types of update and query operations on this sequence:

• 0 l r Set all numbers in the interval $[l, r]$ to $0$.
• 1 l r Set all numbers in the interval $[l, r]$ to $1$.
• 2 l r Flip all numbers in the interval $[l, r]$, that is, change every $0$ to $1$ and every $1$ to $0$.
• 3 l r Query how many $1$s are in the interval $[l, r]$.
• 4 l r Query the maximum number of consecutive $1$s in the interval $[l, r]$.

For each query operation, lxhgww needs to provide an answer. Clever programmers, can you help him?

Input Format

The first line contains two positive integers $n, m$, representing the length of the sequence and the number of operations.
The second line contains $n$ numbers, representing the initial state of the sequence.
Then follow $m$ lines, each containing three integers, representing one operation.

Output Format

For each query operation, output one line with a single integer representing the corresponding answer.

10 10
0 0 0 1 1 0 1 0 1 1
1 0 2
3 0 5
2 2 2
4 0 4
0 3 6
2 3 7
4 2 8
1 0 5
0 5 6
3 3 9

5
2
6
5

Hint

Constraints
For $30\%$ of the testdata, $1 \le n, m \le 1000$.
For $100\%$ of the testdata, $1 \le n, m \le 10^5$.

Translated by ChatGPT 5