题目描述

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

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

输入格式

第一行两个整数 $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\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$。

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