题目描述

给定一个非负整数序列 $a$，初始长度为 $N$。

有 $M$ 个操作，有以下两种操作类型：

• A x：添加操作，表示在序列末尾添加一个数 $x$，序列的长度 $N$ 增大 $1$。
• Q l r x：询问操作，你需要找到一个位置 $p$，满足 $l \le p \le r$，使得：$a[p] \oplus a[p+1] \oplus \dots \oplus a[N] \oplus x$ 最大，输出这个最大值。

输入格式

第一行包含两个整数 $N, M$，含义如问题描述所示。

第二行包含 $N$ 个非负整数，表示初始的序列 $A$。

接下来 $M$ 行，每行描述一个操作，格式如题面所述。

输出格式

每个询问操作输出一个整数，表示询问的答案。

每个答案占一行。

样例

输入样例：

5 5
2 6 4 3 6
A 1 
Q 3 5 4 
A 4 
Q 5 7 0 
Q 3 6 6 

输出样例：

4
5
6

样例解释

初始序列：$[2,6,4,3,6]$，$N=5$

1. A 1 → 在末尾添加 $1$，序列变为 $[2,6,4,3,6,1]$，$N=6$

2. Q 3 5 4：$l=3, r=5, x=4$ 需要找 $p \in [3,5]$ 使 $a[p] \oplus a[p+1] \oplus \dots \oplus a[N] \oplus x$ 最大。 $N=6$，后缀异或和 $S[p] = a[p] \oplus \dots \oplus a[6]$。 我们要最大化 $S[p] \oplus x$。 先计算后缀异或：

   • $S[5] = a[5] \oplus a[6] = 6 \oplus 1 = 7$
   • $S[4] = a[4] \oplus S[5] = 3 \oplus 7 = 4$
   • $S[3] = a[3] \oplus S[4] = 4 \oplus 4 = 0$ 然后计算 $S[p] \oplus 4$：
   • $p=3: 0 \oplus 4 = 4$
   • $p=4: 4 \oplus 4 = 0$
   • $p=5: 7 \oplus 4 = 3$ 最大值为 $4$，输出 $4$。

3. A 4 → 添加 $4$，序列变为 $[2,6,4,3,6,1,4]$，$N=7$

4. Q 5 7 0：$l=5, r=7, x=0$ 计算后缀异或：

   • $S[7] = a[7] = 4$
   • $S[6] = a[6] \oplus S[7] = 1 \oplus 4 = 5$
   • $S[5] = a[5] \oplus S[6] = 6 \oplus 5 = 3$ 计算 $S[p] \oplus 0 = S[p]$：
   • $p=5: 3$
   • $p=6: 5$
   • $p=7: 4$ 最大值为 $5$，输出 $5$。

5. Q 3 6 6：$l=3, r=6, x=6$ 后缀异或：

   • $S[6] = a[6] \oplus a[7] = 1 \oplus 4 = 5$
   • $S[5] = a[5] \oplus S[6] = 6 \oplus 5 = 3$
   • $S[4] = a[4] \oplus S[5] = 3 \oplus 3 = 0$
   • $S[3] = a[3] \oplus S[4] = 4 \oplus 0 = 4$ 计算 $S[p] \oplus 6$：
   • $p=3: 4 \oplus 6 = 2$
   • $p=4: 0 \oplus 6 = 6$
   • $p=5: 3 \oplus 6 = 5$
   • $p=6: 5 \oplus 6 = 3$ 最大值为 $6$，输出 $6$。

数据范围

• $N,M \le 3 \times 10^5$
• $0 \le a[i] \le 10^7$

时空限制

• 时间限制：1 秒
• 空间限制：256 MB