题目背景

O Fortuna velut luna statu variabilis……

（图片来自 Phigros 曲绘，侵删。）

加强版 T512613。

题目描述

Geopelia 需要捕捉到一种特殊的，不同于黑洞的引力波。

第 $i$ 个引力波有着一个频率 $A_i$，而多个引力波会互相影响，叠加，形成一个频率更快的引力波。

具体的，对于一个长度为 $n$ 的序列 $A$，$A$ 中所有引力波叠加起来的频率 $f(A)$ 为：$\bigcup\limits_{i=1}^n A_i$。其中 $\bigcup$ 表示按位或。

现在，Geopelia 需要知道几段以同一引力波开始的区间的频率之和。

也就是说，Geopelia 要向你询问：

$$\sum_{i=l}^rf(A[l,i])$$

的值，其中 $A[l,r]$ 为 $A_l,A_{l+1},\cdots,A_{r-1},A_r$ 组成的序列。

但不幸的是，由于幽蓝边界的引力影响，某一个区间 $[l,r]$ 中所有引力波的频率可能会异或上一个值 $x$。

Geopelia 想实时更新她的数据，你可以帮帮她吗？

她知道引力波的频率可能很高，所以你只需要告诉她答案 $\bmod \ 2^{30}$ 的值就可以了。

形式化题意

给定一个长度为 $n$ 的数组 $A$，你需要完成以下 $q$ 次操作。

1. 1 l r x 将 $A_i(l\le i\le r)$ 异或上 $x$。

2. 2 l r 求：

$$(\sum_{i=l}^r\bigcup_{j=l}^i A_j) \bmod 2^{30}$$

其中 $\bigcup$ 表示按位或。

输入格式

第一行输入两个数 $n$ 和 $q$，代表引力波的数量和操作的次数。

第二行输入 $n$ 个整数，第 $i$ 个数代表引力波 $i$ 初始的频率 $A_i$。

接下来 $q$ 行，每行输入三个整数 $opt,l,r$。

若 $opt=1$，则再输入一个整数 $x$ 表示将区间 $[l,r]$ 中引力波的频率异或上 $x$。

若 $opt=2$，则代表这是一次查询。

输出格式

对于每个查询，输出一行一个整数代表所求式子的值 $\bmod \ 2^{30}$ 的结果。

3 3
1 2 3
2 1 3
1 1 2 2
2 1 3

7
9

提示

样例解释

对于第一组询问：此时 $A=\{1,2,3\}$，所以答案为 $1+1\cup 2+1\cup 2\cup 3=1+3+3=7$。

对于第二组询问：此时 $A=\{3,0,3\}$，所以答案为 $3+3\cup 0+3\cup 0\cup 3=3+3+3=9$。

数据范围

本题使用 subtask 进行捆绑测试，每个 subtask 的具体分值如下：

子任务	$n$	$q$	时间	空间	分值
$0$	$\le 100$		$1s$	$512MB$	$20$
$1$	$\le 2\times 10^4$
$2$	$\le 2\times 10^5$		$3s$
$3$				$\color{red}100MB$	$40$

对于所有数据，满足 $0\le a_i,x< 2^{30}$，$1\le l\le r\le n$。

INITALIZING……
SCANING……
CONNECTING……__PhigrOS Client Login
TIME_OUT!
CONNECTING……__Unknown
SUCCESS!
————————
……九……鸟……
……鸠……！
……喂？
…听得到吗？
鸠?![SIGNAL LOST]