题目描述

给定一个长度为 $N$ 的序列 $A$，并给出 $M$ 次在线询问。对于每次询问，你需要求出区间 $[l, r]$ 内的最大连续子数组异或和。即：

$$\max_{l \leq i \leq j \leq r} (A_i \oplus A_{i+1} \oplus \dots \oplus A_j)$$

询问是在线的，每次询问给出 $x, y$：

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

其中 $\text{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

样例解释

初始状态：
序列 $A = [1, 4, 3]$，$N = 3$，$M = 3$，$\text{lastans} = 0$。

第一次询问 $x = 0, y = 1$：
计算：

$$l = \min(((0 + 0) \bmod 3) + 1, ((1 + 0) \bmod 3) + 1) = \min(1, 2) = 1$$$$r = \max(1, 2) = 2$$

区间为 $[1, 2]$，对应子数组 $[1, 4]$。
连续子数组异或和：

• $1 = 1$
• $4 = 4$
• $1 \oplus 4 = 5$
  最大值为 $5$，输出 $5$，$\text{lastans} = 5$。

第二次询问 $x = 0, y = 1$：
计算：

$$l = \min(((0 + 5) \bmod 3) + 1, ((1 + 5) \bmod 3) + 1) = \min((5 \bmod 3) + 1, (6 \bmod 3) + 1) = \min(2 + 1, 0 + 1) = \min(3, 1) = 1$$$$r = \max(3, 1) = 3$$

区间为 $[1, 3]$，对应子数组 $[1, 4, 3]$。
连续子数组异或和：

• $1 = 1$
• $4 = 4$
• $3 = 3$
• $1 \oplus 4 = 5$
• $4 \oplus 3 = 7$
• $1 \oplus 4 \oplus 3 = 6$
  最大值为 $7$，输出 $7$，$\text{lastans} = 7$。

第三次询问 $x = 4, y = 3$：
计算：

$$l = \min(((4 + 7) \bmod 3) + 1, ((3 + 7) \bmod 3) + 1) = \min((11 \bmod 3) + 1, (10 \bmod 3) + 1) = \min(2 + 1, 1 + 1) = \min(3, 2) = 2$$$$r = \max(3, 2) = 3$$

区间为 $[2, 3]$，对应子数组 $[4, 3]$。
连续子数组异或和：

• $4 = 4$
• $3 = 3$
• $4 \oplus 3 = 7$
  最大值为 $7$，输出 $7$。

数据范围

• $N = 12000$
• $M = 6000$
• $0 < A_i < 2^{31}$
• $0 \leq x, y < 2^{31}$

注意：题目要求在线询问，$\text{lastans}$ 会影响下次询问的区间。