题目

Yu喜欢位与运算和大数字。Yu的朋友Yihuo喜欢位异或运算和小数字。他们是好朋友，每当有人给他们发送一个数组作为礼物时，他们会互相分享这些数字。

对于一个非负整数数组 $p_1, p_2, ..., p_k$，令 $D$ 为数组中所有数字的位与运算结果 ($p_1$$\rm{\\ AND\\ }$$p_2$$\rm{\\ AND\\ }$$...$$\rm{\\ AND\\ }$$p_k$)，令 $X$ 为数组中所有数字的位异或运算结果 ($p_1$$\rm{\\ XOR\\ }$$p_2$$\rm{\\ XOR\\ }$$...$$\rm{\\ XOR\\ }$$p_k$)。Yu 对于 $p_1, p_2, ..., p_k$ 的满意度值为 $D$，Yihuo 对于相同数组的满意度值为 $-X$（注意，Yihuo喜欢小数字，$X$ 越小，Yihuo满意度越高）。

每当他们收到一个非负整数数组 $p_1, p_2, ..., p_k$ 作为礼物时，他们将数组分成两部分，Yu 得到前半部分，Yihuo 得到后半部分。他们切割数组的位置是为了使得他们各自获得的满意度值之和最大。更确切地说，他们在第 $i$ 个数字之后切割数组，其中 $1 \leq i < k$，这样可以最大化 Yu 得到 $p_1, p_2, ..., p_i$ 的满意度值以及 Yihuo 得到 $p_{i+1}, p_{i+2}, ..., p_k$ 的满意度值。

给定一个由 $N$ 个非负整数组成的数组 $A$ 和 $Q$ 个查询。第 $j$ 个查询问："当我们将 $A_{l_j}, A_{l_j+1}, ..., A_{r_j}$ 给 Yu 和 Yihuo 时，他们的满意度值之和是多少？"你的任务是按照给定的顺序回答所有的查询。

注意，每个查询由 $2$ 个整数 $l_j, r_j$ ($1 \leq l_j < r_j \leq N$) 描述，但这些整数并没有直接给出。你必须根据上一个查询的答案计算出这两个整数，如输入部分所述。这意味着你必须按照给定的顺序计算查询的答案。

输入

$N$ $Q$ $A_1$ $A_2$ ... $A_N$ $l'_1$ $r'_1$ $l'_2$ $r'_2$ : $l'_Q$ $r'_Q$

• 第一行，用空格分隔的两个整数 $N$ ($2 \leq N \leq 10^5$) 和 $Q$ ($1 \leq Q \leq 10^5$)，分别表示数组 $A$ 的元素数量和查询数量。
• 第二行，用空格分隔的 $N$ 个整数，第 $i$ 个 ($1 \leq i \leq N$) 整数是 $A_i$ ($0 \leq A_i < 2^{31}$)。
• 接下来的 $Q$ 行是查询的信息。第 $j$ 行 ($1 \leq j \leq Q$) 包含用空格分隔的 $2$ 个整数 $l'_j$ ($1 \leq l'_j \leq N$) 和 $r'_j$ ($1 \leq r'_j \leq N$)。

根据以下方法计算查询中确切的整数 $l_j, r_j$。

• $l_1 = l'_1$, $r_1 = r'_1$
• 对于满足 $2 \leq j \leq Q$ 的所有 $j$，令 $m_{j - 1}$ 为 $(j - 1)$-th 查询的答案。
  • $l_j = ((l'_j + |m_{j - 1}|)$$\rm{\\ MOD\\ }$$N) + 1$
  • $r_j = ((r'_j + |m_{j - 1}|)$$\rm{\\ MOD\\ }$$N) + 1$

注意，每个答案可能是一个负数，$l_j$ 和 $r_j$ 使用 $m_{j - 1}$ 的绝对值来计算。保证 $1 \leq l_j < r_j \leq N$。

输出

输出 $Q$ 行。第 $j$ 行 ($1 \leq j \leq Q$) 应该包含第 $j$ 个查询的答案。请确保在输出末尾插入换行符。

输入示例 1

7 4
7 3 5 4 6 3 1
2 5
2 5
3 4
5 1

输出示例 1

-1
2
2
5

每个查询的答案如下所示。

• 对于第一个查询，$l_1 = 2$，$r_1 = 5$。数字数组 $3, 5, 4, 6$ 将被分为 $3, 5$ 和 $4, 6$，这提供给 Yu 的满意度值 $3$ AND $5 = 1$，Yihuo 的满意度值 $\-(4$ XOR $6) = -2$，总和为 $\-1$。
• 对于第二个查询，$l_2 = (2 + |-1|)$ MOD $7 + 1 = 4$，$r_2 = (5 + |-1|)$ MOD $7 + 1 = 7$。数组 $4, 6, 3, 1$ 将被分为 $4, 6$ 和 $3, 1$，这提供给 Yu 的满意度值 $4$ AND $6 = 4$ 和 Yihuo 的满意度值 $\-(3$ XOR $1) = -2$，总和为 $2$。
• 对于第三个查询，$l_3 = (3 + |2|)$ MOD $7 + 1 = 6$，$r_3 = (4 + |2|)$ MOD $7 + 1 = 7$。数组 $3, 1$ 只能分为 $3$ 和 $1$，这提供给 Yu 的满意度值 $3$ 和 Yihuo 的满意度值 $-1$，总和为 $2$。
• 对于第四个查询，$l_4 = (5 + |2|)$ MOD $7 + 1 = 1$，$r_4 = (1 + |2|)$ MOD $7 + 1 = 4$。数组 $7, 3, 5, 4$ 将被分为 $7$ 和 $3, 5, 4$，这提供给 Yu 的满意度值 $7$ 和 Yihuo 的满意度值 $\-(3$ XOR $5$ XOR $4) = -2$，总和为 $5$。

输入示例 2

20 30
1 4 3 6 9 9 6 7 5 3 5 4 9 4 1 2 14 5 11 1
14 18
4 15
2 10
3 13
20 15
7 12
18 10
9 15
20 12
5 7
6 10
8 12