Description
FOTILE得到了一个长为N的序列A，为了拯救地球，他希望知道某些区间内的最大的连续XOR和。
即对于一个询问，你需要求出max(Ai xor Ai+1 xor Ai+2 ... xor Aj)，其中l<=i<=j<=r。
为了体现在线操作，对于一个询问(x,y)：
l=min(((x+lastans)mod N)+1,((y+lastans)mod N)+1).
r=max(((x+lastans)mod N)+1,((y+lastans)mod N)+1).
其中lastans是上次询问的答案，一开始为0。
Input
第一行两个整数N和M。
第二行有N个正整数，其中第i个数为Ai，有多余空格。
后M行每行两个数x,y表示一对询问。
Output
共M行，第i行一个正整数表示第i个询问的结果。
Sample Input
3 3
1 4 3
0 1
0 1
4 3
1 4 3
0 1
0 1
4 3
Sample Output
5
7
7
7
7
HINT
N=12000，M=6000，x,y,Ai在signed longint范围内。
题解：
把元素数组aa替换为前缀异或和数组qz，则询问变成了指定区间内最大的两个元素异或和。
假如某个元素x已经确定，那么我们只要在区间中找到一个数y，使x xor y最大。
这可以用字典树在O(log)的复杂度内实现。因为是指定的一个区间，所以要采用可持久化字典树。
为了减少复杂度，采取分块的做法。
将n分为√n块，对于每块的第一个元素i，用a[i,j]表示i到j的区间中的最大连续异或和。
转移方式：a[i,j]:=max(a[i,j-1],qz[j]在[i,j-1]的字典树中的最大异或和)。
注意不要忘了以[i,j]异或和作为答案的情况（即qz[i-1]xor qz[j]）。
预处理好a数组后，开始处理询问[l,r]。
找到第一个比l大的分块首元素i（i=k*√n+1），分情况讨论。
若r≥i，则答案为max(a[i,r],qz[l≤j≤i-1]在[j+1,r]的字典树中的最大异或和)；
若r<i，则答案为max(qz[l≤j≤r]在[l,j-1]的字典树中的最大异或和)，注意考虑以[l,j]异或和作为答案的情况（即qz[l-1]xor qz[j])。
代码：
uses math;
var
t:array[..,..,..]of longint;
a:array[..,..]of longint;
qz,aa:array[..]of longint;
r:array[..]of longint;
b:array[..]of longint;
i,ii,j,k,n,m,block,mm,cnt,x,y,ans:longint;
l,ll,rr:int64;
procedure cl(y,yy,z:longint);
var i:longint;
begin
if z=- then exit;
i:=x and( shl z);
if i> then
begin
inc(cnt); t[yy,]:=t[y,];
t[yy,,]:=cnt; t[yy,,]:=t[y,,]+;
cl(t[y,,],t[yy,,],z-); exit;
end;
inc(cnt); t[yy,]:=t[y,];
t[yy,i,]:=cnt; t[yy,i,]:=t[y,i,]+;
cl(t[y,i,],t[yy,i,],z-);
end;
function qq(y,yy,z:longint):longint;
var i:longint;
begin
if z=- then exit();
i:=x and( shl z);
if i> then
begin
if t[yy,,]-t[y,,]> then
exit(b[z]+qq(t[y,,],t[yy,,],z-));
exit(qq(t[y,,],t[yy,,],z-));
end;
if t[yy,,]-t[y,,]> then
exit(b[z]+qq(t[y,,],t[yy,,],z-));
exit(qq(t[y,,],t[yy,,],z-));
end;
begin
b[]:=;
for i:= to do b[i]:=b[i-]*;
readln(n,m);
for i:= to n do
begin
read(aa[i]); qz[i]:=aa[i] xor qz[i-]; x:=qz[i];
inc(cnt); r[i]:=cnt; cl(r[i-],cnt,);
end;
block:=trunc(sqrt(n)*1.5)+;
block:=min(n,block);
i:=;
while i<=n do
begin
inc(mm);
a[mm,i]:=aa[i];
for j:=i+ to n do
begin
x:=qz[j]; a[mm,j]:=max(a[mm,j-],x xor qz[i-]);
a[mm,j]:=max(a[mm,j],qq(r[i-],r[j-],));
end;
i:=i+block;
end;
for i:= to m do
begin
readln(ll,rr);
l:=max((ll+ans)mod n+,(rr+ans)mod n+);
ll:=min((ll+ans)mod n+,(rr+ans)mod n+);
k:=l; j:=ll; l:=;
while block*l+<=j do inc(l);
if block*l+<=k then
begin
ans:=a[l+,k]; l:=block*l;
for ii:=j to l do
begin
x:=qz[ii-];
ans:=max(ans,qq(r[ii-],r[k],));
end;
end else
begin
ans:=aa[j];
for ii:=j+ to k do
begin
x:=qz[ii]; ans:=max(ans,x xor qz[j-]);
ans:=max(ans,qq(r[j-],r[ii-],));
end;
end;
writeln(ans);
end;
end.