将后缀异或和转化为两个前缀异或和的异或和。
设 s[i] 表示直到 a[i] （包括 a[i]）的前缀异或和。
每次查询就转化为：给定 l,r 找一个最大的 p ($l-1 \le p \le r-1$), 使得 s[p] xor s[n] xor x 最大。
如果 p 的范围只有 $\le r-1$ 的限制， 就可以直接可持久化 0/1 Trie 做了。

考虑给 Trie 的节点增加额外的信息， 使得不至于在查询的过程中走到 $< l-1$ 的节点 : 在可持久化 Trie 中插入数的时候， 给新建的节点染色，这样， 如果一个节点的颜色是位置 $l-1<$ 的数的颜色， 这说明以这个节点为根的子树内只有位置 $< l-1$ 的数的终止节点， 在 Trie 中游走的时候避免走这类点， 就可以在满足 $\le r-1$ 限制的同时满足 $\ge l-1$ 的限制。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 600003;

int n,m,las;
int tot, root[N], ch[N*24][2], col[N*24];

void insert(int id, int tmp) {
  int p = root[id-1], q = root[id] = ++tot;
  col[q] = id;
  for(int i=23;i>=0;--i) {
    int v = (tmp>>i)&1;
    col[ch[q][v] = ++tot] = id;
    ch[q][v^1] = ch[p][v^1];
    q = ch[q][v];
    p = ch[p][v];
  }
}

int ques(int id, int underlim, int tmp) {
  int res = 0;
  int p = root[id];
  for(int i=23;i>=0;--i) {
    int v = (tmp>>i)&1;
    if(ch[p][v^1] && col[ch[p][v^1]] >= underlim) res += (1<<i), p = ch[p][v^1];
    else p = ch[p][v];
  }
  return res;
}

int main() {

  scanf("%d%d", &n,&m);
  for(int i=1, a; i<=n; ++i) {
    scanf("%d", &a);
    las = las ^ a;
    insert(i, las);
  }
  char s[3];
  int l,r,x;
  while(m--)
  {
    scanf("%s", s);
    if(s[0] == 'A')
    {
      scanf("%d", &x);
      las = las ^ x;
      insert(++n, las);
    }
    else
    {
      scanf("%d%d%d", &l, &r, &x);
      if(r==1) {
        cout << (las ^ x) << '\n';
        continue;
      }
      cout << ques(r-1, l-1, x ^ las) << '\n';
    }
  }
  return 0;
}