Description

Let $x$ be a $01$ string with length at least $2$. If the XOR of every length $2$ substring of $x$ is $1$, then $x$ is called a "VS string".

You need to maintain a $01$ string $a$ of length $n$, supporting the following operations:

$$\def\arraystretch{1.5} \begin{array}{|c|c|} \hline \textbf{Format} & \textbf{Description} \cr\hline \texttt{0 l r} & \text{Fill the interval }[l,r]\text{ with }0 \cr\hline \texttt{1 l r}& \text{Fill the interval }[l,r]\text{ with }1 \cr\hline \texttt{2 l r}& \text{Flip every bit in }[l,r]\text{, i.e., }1\text{ becomes }0\text{ and }0\text{ becomes }1 \cr\hline \texttt{3 l r k} & \text{Query how many substrings of length }k\text{ in }[l,r]\text{ are "VS strings"} \cr\hline \texttt{4 l r} & {\def\arraystretch{1}\begin{array}{c} \text{Query the length of the longest "VS string" within }[l,r]\text{,}\\\text{and output }1\text{ if no such substring exists in the interval} \end{array}} \cr\hline \end{array}$$

Input Format

The first line contains two integers $n,m$, representing the length of the $01$ string and the number of operations.
The second line contains $n$ integers, representing $a_1,a_2,\cdots,a_n$.
The next $m$ lines each contain three or four integers $op, l, r(,k)$, representing one operation.

Output Format

For each query operation, output one integer per line, representing the corresponding answer.

5 7
0 1 1 0 1
0 1 2
2 1 5
3 1 5 3
2 1 3
2 2 3
3 1 5 3
4 1 5

2
3
5

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

1
3
2
0
1
3
2
2
3

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

4
0
1
1
3
2

Hint

Sample Explanation

Sample #1

Number of operations	Input content	$01$ string	Answer
$0$	$/$	$01101$	$/$
$1$	0 1 2	$00101$
$2$	2 1 5	$11010$
$3$	3 1 5 3		$2$
$4$	2 1 3	$00110$	$/$
$5$	2 2 3	$01010$
$6$	3 1 5 3		$3$
$7$	4 1 5		$5$

---

Constraints

This problem uses bundled testdata.

For all testdata, $0\le op \le 4$, $1 \le l \le r \le n\le3\times10^5$, $3 \le k \le n$, $1\le m \le 5 \times 10^5$.

subtask	Score	$4\le n,m \le$	Time limit	Special property
$1$	$10$	$10^3$	$300$ ms	None
$2$	$15$	$10^5$	$1000$ ms	No operations $0,1,2$
$3$			$2000$ ms	No operation $3$
$4$				$op,l,r,a_i$ are generated uniformly at random within their ranges
$5$			$3000$ ms	$k=3$
$6$	$10$			None
$7$	$20$	$5\times10^5$	$2000$ ms	$n\le3\times10^5$

This problem may be slightly strict on constant factors.
The time limits are designed to keep the total time limit of all test points within $120$s and to eliminate incorrect algorithms.

Translated by ChatGPT 5