Description:


给定一个非负整数序列 \({a_i}\) ,初始长度为 \(N\)
\(M\) 个操作,有以下两种操作类型:

  1. A x:添加操作,表示在序列末尾添加一个数 \(x\) ,序列的长度 \(N+1\)
  2. Q l r x:询问操作,你需要找到一个位置 \(p\) ,满足 \(l\le p\le r\) ,使得: \(a_p\ xor\ a_{p+1}\ xor\ ...\ xor\ a_N\ xor\ x\) 最大,输出最大是多少。

Input:


第一行包含两个整数 \(N\)\(M\) ,含义如问题描述所示。
第二行包含 \(N\) 个非负整数,表示初始的序列 \({a_i}\)
接下来 \(M\) 行,每行描述一个操作,格式如题面所述。

Output:


假设询问操作有 \(T\) 个,则输出应该有 \(T\) 行,每行一个整数表示询问的答案。

Sample Input:


Sample Output:


HINT:


对于测试点1-2, \(N,M\le 5\)
对于测试点3-7, \(N,M\le 80000\)
对于测试点8-10, \(N,M\le 300000\)
其中测试点1,3,5,7,9保证没有修改操作。
对于 100% 的数据, \(0\le a_i\le 10^7\)

题解:


根本没有想到可持久化字典树。

\(b_x = a_1\ xor\ a_2\ xor\ a_3\ ...\ a_x\)
那么询问要求最大化的就是 \(b_n\ xor\ x\ xor\ b_p\) ,其中 \(p\in [l-1, r-1]\)

然后我们可以用可持久化字典树得到这段区间的一棵字典树。
贪心一下就可以了。