题目描述

设 $x$ 为一个长度不小于 $2$ 的 $01$ 串，如果 $x$ 的所有长度为 $2$ 的子串的异或和均为 $1$，则 $x$ 为一个「VS 串」。

你需要维护一个长度为 $n$ 的 $01$ 串 $a$，支持以下操作：

$$\def\arraystretch{1.5} \begin{array}{|c|c|} \hline \textbf{格式} & \textbf{说明} \cr\hline \texttt{0 l r} & \text{将区间 }[l,r]\text{ 填充为 }0 \cr\hline \texttt{1 l r}& \text{将区间 }[l,r]\text{ 填充为 }1 \cr\hline \texttt{2 l r}& \text{将区间 }[l,r]\text{ 中的每个数取反，即 }1\text{ 变 } 0\text{，}0\text{ 变 }1 \cr\hline \texttt{3 l r k} & \text{查询}[l,r]\text{ 区间中有多少个长度为 }k\text{ 的子串是「VS 串」} \cr\hline \texttt{4 l r} & {\def\arraystretch{1}\begin{array}{c} \text{查询 }[l,r]\text{ 区间内最长的「VS 串」的长度，}\\\text{如果区间内不存在这样的子串则输出 }1 \end{array}} \cr\hline \end{array} $$

输入格式

第一行两个整数 $n,m$，表示 $01$ 串长度与操作个数。
第二行 $n$ 个整数，表示 $a_1,a_2,\cdots,a_n$。
接下来 $m$ 行，每行三或四个整数 $op, l, r(,k)$，表示一次操作。

输出格式

对于每个查询操作，输出一行一个整数，表示其对应的答案。

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

提示

样例解释

样例 #1

操作次数	输入内容	零一串	答案
$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$

---

数据范围

本题采用捆绑测试。

对于所有数据，有 $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	分值	$4\le n,m \le$	时间限制	特殊性质
$1$	$10$	$10^3$	$300$ ms	无
$2$	$15$	$10^5$	$1000$ ms	没有 $0,1,2$ 操作
$3$			$2000$ ms	没有 $3$ 操作
$4$				$op,l,r,a_i$ 在其数据范围内等概率随机生成
$5$			$3000$ ms	$k=3$
$6$	$10$			无
$7$	$20$	$5\times10^5$	$2000$ ms	$n\le3\times10^5$

本题可能略微卡常。
这样设计时间限制是为了让测试点总时间限制在 120s 以内并且卡掉错误算法。