题目描述

FOTILE得到了一个长为$\red {N}$的序列$\red {A}$，为了拯救地球，他希望知道某些区间内的最大的连续$\red {XOR}$和。

即对于一个询问，你需要求出$\red {max(A_i ~xor~ A_{[i+1]} ~xor ~A_{[i+2]} … xor~ A_j)}$，其中$\red {l<=i<=j<=r}$。

为了体现在线操作，对于一个询问$\red {(x,y)}$：

$\red {l = min ( ((x+lastans)~ mod~ N)+1 , ((y+lastans) ~mod ~N)+1 )}$

$\red {r = max ( ((x+lastans)~ mod~ N)+1 , ((y+lastans) mod ~N)+1 )}$

其中$\red {lastans}$是上次询问的答案，一开始为$\red {0}$。

输入格式

第一行两个整数$\red {N}$和$\red {M}$。

第二行有$\red {N}$个正整数，其中第$\red {i}$个数为$\red {A_i~}$。

后$\red {M}$行每行两个整数$\red {x,y}$表示一对询问。

输出格式

共$\red {M}$行，每行输出一个正整数，第$\red {i}$行的正整数表示第$\red {i}$个询问的结果。

样例

输入样例

3 3
1 4 3
0 1
0 1
4 3

输出样例

5
7
7

提示

$\red {N=12000，M=6000，0<x,y,A _i~ <2^{31}}$