题目描述

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

有 $\red {M}$ 个操作，有以下两种操作类型：

1、$\red {”A x”}$：添加操作，表示在序列末尾添加一个数 $\red {x}$，序列的长度 $\red {N}$ 增大$\red {1}$

2、$\red {”Q~ l ~r ~x”}$：询问操作，你需要找到一个位置 $\red {p}$，满足$\red {l≤p≤r}$，使得：$\red {a[p] ~xor~ a[p+1] ~xor … xor~ a[N] ~xor~ x}$ 最大，输出这个最大值。

输入格式

第一行包含两个整数 $\red {N，}$，含义如问题描述所示。

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

接下来$\red { 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

提示

$\red {N,M≤3\times10 ^5 ,0≤a[i]≤10 ^7}$ 。