「集训队互测」是由 CCF 自主研发的一款开放算法竞赛游戏，在这里，最强的参赛选手将成为「集集国王」，导引 OI 之力，击败强大的题目，找回失散的 IOI 金牌。
要想成为「集集国王」，你就要先打败「异或尊主」（The Xor Master）。
「异或尊主」向你发起了挑战：
题目描述
下文中将异或符号记作 $ \oplus $。
「异或尊主」有一个长为 $ n $ 的序列 $ a $，和一个初始为空的集合 $ S_0 $。
定义 $ \operatorname{xor}(S) $ 表示集合 $ S $ 中所有元素的异或和，若 $ S $ 为空则是 $ 0 $。
定义 $ g(x,S)=\max\limits_{T\subseteq S} (x\oplus \operatorname{xor}(T)) $。
定义 $ f(l,r)=g(\oplus_{i=l}^{r} a_i, S_0) $，$ \oplus_{i=l}^{r}a_i $ 表示 $ a_l\sim a_r $ 的异或和。
「异或尊主」会进行 $ Q $ 次操作或询问：
1 x v：将 $ a_x $ 异或上 $ v $ 。2 x：将 $ x $ 加入集合 $ S_0 $ 中。3 l r：询问 $ \sum\limits_{i=l}^r f(l,i) $ 的值。由于答案可能很大，只需要输出答案 $ \bmod 2^{64} $ 的值。
你急于成为「集集国王」，请快速回答出「异或尊主」的询问来将他打败吧！
输入格式
第一行两个整数 $ n,Q $。
第二行 $ n $ 个非负整数 $ a_1\sim a_n $。
接下来 $ Q $ 行，每行描述一次操作或询问，格式见题目描述。
输出格式
对于每次询问输出一行一个整数，表示答案 $ \bmod 2^{64} $ 的值。
样例
input 1
5 5
5 7 1 4 3
3 1 3
1 2 4
3 1 5
2 3
3 1 5
output 1
10
21
25
input 2
5 6
0 6 9 8 3
3 2 5
1 3 6
3 2 5
1 4 1
2 3
3 1 5
output 2
32
18
25
数据范围
| 子任务编号 | 分值 | $n \leq$ | $Q \leq$ | $m = $ | 特殊性质 |
|---|---|---|---|---|---|
| $1$ | $10$ | $2000$ | $2\,000$ | $32$ | 无 |
| $2$ | $10$ | $5 \times 10^5$ | $10^5$ | $64$ | A,B |
| $3$ | $10$ | B | |||
| $4$ | $10$ | $10^5$ | $32$ | A,C | |
| $5$ | $15$ | $5 \times 10^5$ | $64$ | ||
| $6$ | $15$ | $10^5$ | $32$ | 无 | |
| $7$ | $30$ | $5 \times 10^5$ | $64$ |