「QMSOI R1」 Distorted Fate
题目背景
**O Fortuna velut luna statu variabilis……**
（图片来自 Phigros 曲绘，侵删。）
加强版 [T512613](https://www.luogu.com.cn/problem/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}$ 的结果。
输入输出样例
输入样例 #1
3 3
1 2 3
2 1 3
1 1 2 2
2 1 3输出样例 #1
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$ | $\le 100$ | $1s$ | $512MB$ | $20$ |
| $1$ | $\le 2\times 10^4$ | $\le 2\times 10^4$ | $1s$ | $512MB$ |$20$ |
| $2$ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | $3s$ | $512MB$ |$20$ |
| $3$ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | $3s$ | $\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]
```