附加文件

Description

N 头奶牛排成一队，第 i 头奶牛的身高为 Hi。可能有的奶牛身高为 0。

Farmer John 有 M 个操作，这些操作分成两种类型：

• A 操作，格式为 A h ，表示有一头身高为 h 的奶牛添加到了队伍的最后面，此时奶牛的数目 N 的值相应加 1.

• Q 操作，格式为 Q x y z ，表示 John 希望找到一个整数 t，满足 x ≤ t ≤ y，并且 H[t] ⊕ H[t+1] ⊕ … ⊕ H[N] ⊕ z 的值最大。其中的符号 ⊕ 表示异或。注意：此时的 N 值为当前最新的 N 值。

自然地，John 找到了你，请你帮助 John 输出每个 Q 操作所得到的异或和的最大值。

Input

第一行：两个整数 N, M。

第二行：N 个非负整数，表示 Hi。

接下来 M 行，每行描述一个操作。

Output

对于每个 Q 操作，按输入顺序依次输出对应的答案，每个答案占一行。

Sample Input

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

Sample Output

4 
5 
6 

Data Size

共 10 个测试点，全部满足 0 ≤ Hi ≤ 10^7。其中：

• 有 2 个测试点：N, M ≤ 10 且其中 1 个测试点没有 A 操作。
• 有 5 个测试点：N, M ≤ 100000 且其中 3 个测试点没有 A 操作。
• 有 3 个测试点：N, M ≤ 300000 且其中 1 个测试点没有 A 操作。