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

数据范围