「集训队互测」是由 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

数据范围

特殊性质 $\mathrm{A}$：不存在 1 类操作。

特殊性质 $\mathrm{B}$：不存在 2 类操作。

特殊性质 $\mathrm{C}$：对于所有询问，保证 $l=1$。