「集训队互测」是由 CCF 自主研发的一款开放算法竞赛游戏,在这里,最强的参赛选手将成为「集集国王」,导引 OI 之力,击败强大的题目,找回失散的 IOI 金牌。
要想成为「集集国王」,你就要先打败「异或尊主」(The Xor Master)。
「异或尊主」向你发起了挑战:
题目描述
下文中将异或符号记作 ⊕。
「异或尊主」有一个长为 n 的序列 a,和一个初始为空的集合 S0。
定义 xor(S) 表示集合 S 中所有元素的异或和,若 S 为空则是 0。
定义 g(x,S)=maxT⊆S(x⊕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 |