XOR and Afterimage

• 时间限制：$1$ 秒
• 空间限制：$512\text{ MB}$

题目描述

给定长度为 $n$ 的非负整数序列 $a$，$q$ 次操作，每次操作为以下三种中的一种：

• 1：对于所有 $i\in[1,n)$，同时将 $a_i$ 改为 $a_i\oplus a_{i+1}$；
• 2：对于所有 $i\in(1,n]$，同时将 $a_i$ 改为 $a_i\oplus a_{i-1}$；
• 3 l r：求 $\bigoplus_{i=l}^ra_i$。

输入格式

第一行输入两个正整数 $n,q$。

第二行输入 $n$ 个非负整数，代表序列 $a$。

接下来 $q$ 行，每行一或三个正整数，代表一次操作。

输出格式

对于每次 3 操作，输出一行一个数，代表答案。

输入输出样例 #1

输入 #1

5 5
1 4 5 2 6
1
3 2 4
2
3 2 4
3 1 1

输出 #1

2
1
5

输入输出样例 #2

输入 #2

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

输出 #2

8
11
6

说明/提示

对于所有数据，保证：

• $1\le n\le 3\times 10^5$；
• $1\le q\le 3\times 10^5$；
• $0\le a_i<2^{30}$。

本题采用捆绑测试，各子任务特殊性质如下：

特殊性质 A：没有操作 $2$。

特殊性质 B：操作 $3$ 次数不超过一次。