异或满足可减性，所以可以维护前缀和，然后  
      a[p] xor a[p + 1] xor ... xor a[n] xor = s[p - 1] xor s[n] xor
      
然后就只要维护s[]。添加很好维护，重点是如何查询

此时查询转变为：val = s[n] xor x，求一个p∈[l - 1, r - 1]使得s[p] xor val最大

可以构建一颗可持久化Trie，第i个版本为插入了s[i]后的Trie树。


每次查询，从根节点开始，贪心地选与这一位相反的值。

此外，还有一个l−1≤p≤r−1的限制。

先考虑p≤r−1，查询第r−1个版本的Trie即可，因为此时不可能访问到r-1r−1之后的ss。 再考虑l−1≤p，对每个节点维护一个latest值，表示子树中所有ss值的下标的最大值。这样，在查询时只访问latest≥l−1的节点就行了。


#include <bits/stdc++.h>
using namespace std;
const int maxn = 6e5 + 5;
struct Node {
	int son[2], cnt;
}trie[maxn * 30];

int n, m, tot, ans, rt[maxn];
char opt[2];

void insert(int &x, int y, int d, int num) {
	x = ++tot;
	trie[x] = trie[y];
	trie[x].cnt++;
	if (d < 0) {
		return ;
	}
	int t = num & (1 << d) ? 1 : 0;
	insert(trie[x].son[t], trie[y].son[t], d - 1, num);
}

void query(int x, int y, int d, int num) {
	if (d < 0) {
		return ;
	}
	int t = num & (1 << d) ? 1 : 0;
	int dl = trie[trie[x].son[t ^ 1]].cnt;
	int dr = trie[trie[y].son[t ^ 1]].cnt;
	if (dr - dl) {
		ans |= (1<< d);
		query(trie[x].son[t ^ 1], trie[y].son[t ^ 1], d - 1, num);
	} else {
		query(trie[x].son[t], trie[y].son[t], d - 1, num);
	}
}

int main() {
	scanf("%d%d", &n, &m);
	n++;
	int sum = 0, l, r, x;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &x);
		sum ^= x;
		insert(rt[i], rt[i - 1], 24, sum);
	}
	while (m--) {
		scanf("%s", opt);
		if (opt[0] == 'A') {
			scanf("%d", &x);
			sum ^= x;
			insert(rt[++n], rt[n], 24, sum);
		} else {
			scanf("%d%d%d", &l, &r, &x);
			x ^= sum; ans = 0;
			l++; r++;
			query(rt[l - 2], rt[r - 1], 24, x);
			printf("%d\n", ans);
		}
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int maxn = 6e5 + 5;
struct Node {
	int son[2], cnt;
}trie[maxn * 30];
int n, m, tot, ans, rt[maxn];
int opt[2];

void insert(int &nowp, int last, int d, int num) {
	nowp = ++tot;
	trie[nowp] = trie[last];
	trie[nowp].cnt++;
	if (d < 0) {
		return;
	}
	int t = num & (1 << d) ? 1 : 0;
	insert(trie[nowp].son[t], trie[last].son[t], d - 1, num);
}

void query(int nowp, int last, int d, int num) {
	if (d < 0) {
		return ;
	}
	int t = num & (1 << d) ? 1 : 0;
	int dr = trie[trie[nowp].son[t ^ 1]].cnt;
	int dl = trie[trie[last].son[t ^ 1]].cnt;
	if (dr - dl) {
		ans |= (1 << d);
		query(trie[nowp].son[t ^ 1], trie[last].son[t ^ 1], d - 1, num);
	} else {
		query(trie[nowp].son[t], trie[last].son[t], d - 1, num);
	}
}


int main() {
	scanf("%d%d", &n, &m);
	int x, l, r;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &x);
		insert(rt[i], rt[i - 1], 30, x);
	}
	while (m--) {
		scanf("%d%d%d", &x, &l, &r); ans = 0;
		query(rt[r + 1], rt[l], 30, x);
		printf("%d\n", ans);
	}
	return 0;
}