题目描述

给定长度为 $n$ 的序列 $a$，支持 $q$ 次操作，每次操作形如以下两种中的一种：

• 1 l r x：对所有 $i\in[l,r]$，将 $a_i$ 异或上 $x$。
• 2 l r：求区间 $[l,r]$ 所有子区间权值按位或的异或和。

输入格式

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

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

接下来 $q$ 行，每行一次操作，格式如题目描述所示。

输出格式

对于每次询问，输出一行一个数，代表答案。

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

0
4
0
4

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

6
0

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

4
4
0

提示

【样例解释】

以下 $\operatorname{or}$ 表示按位或运算，$\operatorname{xor}$ 表示按位异或运算。

对于第一组样例的第二个询问，区间 $[2,4]$ 所有子区间按位或的异或和等于 $a_2\operatorname{xor}a_3\operatorname{xor}a_4\operatorname{xor}(a_2\operatorname{or}a_3)\operatorname{xor}(a_3\operatorname{or}a_4)\operatorname{xor}(a_2\operatorname{or}a_3\operatorname{or}a_4)$，等于 $4$。

【数据范围】

对于所有数据，保证：

• $1\le n,q\le 5\times10^5$
• $0\le a_i,x<2^{60}$
• $1\le l\le r\le n$

本题采用打包测试，各测试包描述如下：