做法：可持久化01tire

思路：

令s[i] = a[1] ^ a[2] ^ … a[i-1] ^ a[i]
则a[p] xor a[p+1] xor … xor a[N] xor x 相当于 s[N] ^ x ^ s[p-1]
s[N] ^ x 每次可以看成一个固定值 v提前算出来, 则相当于 求 l-1 <= p-1 <= r-1 使得 v 与 s[p-1]异或最大

s[p-1]的二进制最高位开始到最低位的每一个数字尽量与v的二进制对应位相反就可以保证异或出来最大。
s的每个版本可以看成是持久化的trie记录下来。
对持久化trie的每个节点额外维护一个信息max_id，表示其所属的持久化版本，显然一个节点的max_id等于其子节点中最大的版本号（因为子节点要么是连向之前的版本，要么创建了该节点后再创建子节点）。 如果一个节点的max_id 小于l-1，说明这个节点是s[l-1]插入之前就已经创建出来的节点，不应该考虑在内。

代码

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp(aa,bb) make_pair(aa,bb)
#define _for(i,b) for(int i=(0);i<(b);i++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,b,a) for(int i=(b);i>=(a);i--)
#define mst(abc,bca) memset(abc,bca,sizeof abc)
#define X first
#define Y second
#define lowbit(a) (a&(-a))
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long double ld;
const int N=6e5+10;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-6;

int s[N];

struct Trie {
    int root[N],nex[N*32][2],cnt=0;
    int max_id[N*32];
    void insert(int k) {
        int p,q;
        if(!k) p=0,q=root[k];
        else p=root[k-1],q=root[k];
        max_id[q]=k;
        for (int i = 30; i >= 0; i--) {
            int c=s[k]>>i&1;
            if(p) nex[q][c^1]=nex[p][c^1];
            nex[q][c] = ++cnt;
            max_id[nex[q][c]]=k;
            p=nex[p][c],q=nex[q][c];
        }
    }
    int query(int p,int l,int x) {
        for (int i = 30; i >= 0; i--) {
            int c = x>>i&1;
            if(max_id[nex[p][c^1]]>=l) p=nex[p][c^1];
            else p=nex[p][c];
        }
        return x^s[max_id[p]];
    }
} t;


int main() {
    ios::sync_with_stdio(0);cin.tie(0);
#ifdef DEBUG
    freopen("F:/laji/1.in", "r", stdin);
//    freopen("F:/laji/2.out", "w", stdout);
#endif
    int n,m;cin>>n>>m;
    t.max_id[0]=-1; //-1表示不存在 
    // t.root[0]=++t.cnt;
    // t.insert(0);
    rep(i,1,n){
        int a;cin>>a;
        s[i]=s[i-1]^a;
        t.root[i]=++t.cnt;
        t.insert(i);
    } 
    while(m--){
        char op;cin>>op;
        if(op=='A'){
            int x;cin>>x;
            t.root[++n]=++t.cnt;
            s[n]=s[n-1]^x;
            t.insert(n);
        }
        else{
            int l,r,x;cin>>l>>r>>x;
            cout<<t.query(t.root[r-1],l-1,s[n]^x)<<"\n"; 
        }
    }
    return 0;
}