/*
目标:找到l<= p <= r, 使得a[p] ^ a[p + 1] ^ ... ^ a[n] ^ x 最大
即使:s[p - 1] ^ s[n] ^ x 最大,s[n] ^ x 为定值令其为C
即找到s[p - 1] ^ C 最大
即在l-1<= i <= r-1, 使得s[i] ^ C最大
即在第r - 1个版本里面找到一个s[i]使得s[i] ^ C最大 且 i >= l-1 !!
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
//最多会有N个数,每个数最大为1e7,有24位,加上根节点,就会有25 * N个节点
const int N = 6e5 + 10, M = 25 * N;
/*
s[i]:前i个数的异或值
root[i]:表示第i的版本的根节点
max_idx[i]:以第i个节点为根的子树最大下标
tr[i][0/1]:第i个节点的左右儿子(0/1)的值
*/
int s[N], root[N], idx;
int tr[M][2], max_id[M];
int n, m;
/*
i:异或前缀和下标
k:当前为第k位
p:上个版本
q:当前版本
*/
void insert(int i, int k, int p, int q)
{
//此时q:s[i]的叶节点,那么max_id[p]即为i
if(k < 0)
{
max_id[q] = i;
return ;
}
//u: s[i]的第k位
int u = s[i] >> k & 1;
//如果p(上个版本存在),就让q(当前版本)的另一个儿子(tr[q][u ^ 1]) 继承上个版本的部分(tr[p][u ^ 1])
if(p) tr[q][u ^ 1] = tr[p][u ^ 1];
//给新的这个儿子分配一个节点
tr[q][u] = ++ idx;
//递归找下去
insert(i, k - 1, tr[p][u], tr[q][u]);
//用该节点的两个儿子更新该节点的最大值
max_id[q] = max(max_id[tr[q][0]], max_id[tr[q][1]]);
}
/*
L:表示区间左限制:l-1
root:表示r-1的节点
C:表示s[n] ^ x
*/
int query(int L, int root, int C)
{
int p = root;
for(int i = 23; i >= 0; i--)
{
int u = C >> i & 1;
//要找异或最大就要找u的对立面是否存在而且要大于限制L
if(max_id[tr[p][u ^ 1]] >= L) p = tr[p][u ^ 1];//u的对立面存在且大于L就向下找
else p = tr[p][u];//不存在就在该节点向下找
}
//此时的max_id[p]为叶节点的max_id[p]也就是我们要找的那个异或前缀的下标
return C ^ s[max_id[p]];
}
int main()
{
scanf("%d%d", &n, &m);
max_id[0] = -1;
root[0] = ++idx;
insert(0, 23, 0, root[0]);
for(int i = 1; i <= n; i ++)
{
int x;
scanf("%d", &x);
s[i] = s[i - 1] ^ x;
root[i] = ++idx;
insert(i, 23, root[i - 1], root[i]);
}
int l, r, x;
char op[2];
while(m--)
{
scanf("%s", op);
if(*op == 'A')
{
scanf("%d", &x);
n ++;
s[n] = s[n - 1] ^ x;
root[n] = ++ idx;
insert(n, 23, root[n - 1], root[n]);
}
else
{
scanf("%d%d%d", &l, &r, &x);
printf("%d\n", query(l - 1, root[r - 1], s[n] ^ x));
}
}
return 0;
}