题目描述

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

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

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

• $l=min(((x+lastans)\bmod N)+1,((y+lastans)\bmod N)+1)$
• $ r=max(((x+lastans)\bmod N)+1,((y+lastans)\bmod N)+1)$

其中 lastans 是上次询问的答案，一开始为 0。

输入格式

第一行两个整数 $N$ 和 $M$。

第二行有 $N$个正整数，其中第 $i$个数为$A_i$。

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

输出格式

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

样例

3 3
1 4 3
0 1
0 1
4 3

5
7
7

数据范围

$N=12000，M=6000，0<A_i<2^{31}，0≤x,y<2^{31}$

来源

• BZOJ2741
• 算法竞赛进阶指南