「XSOI-R1」区间操作

小 A 喜欢区间操作问题。

小 A 给你了一个长度为 $n$ 的序列 $a$，并给你了 $q$ 组询问。 对于每组询问，小 A 会给你两个正整数 $l,r$，你需要求出 $(a_l) \oplus (a_l+a_{l+1}) \oplus (a_l+a_{l+1}+a_{l+2}) \oplus \dots \oplus (a_l + a_{l+1} + a_{l+2} + \dots + a_r)$ 的值。 其中 $\oplus$ 表示异或运算。

第一行两个正整数 $n,q$， 之后一行 $n$ 个整数 $a_i$， 之后 $q$ 行每行两个正整数 $l,r$。

共 $q$ 行， 每行一个整数表示你的答案。

6 1
1 1 4 5 1 4
1 6

18

7 10
1 9 1 9 8 1 0
1 2
1 3
1 4
1 5
1 6
1 7
2 6
3 5
4 7
2 7

11
0
20
8
21
8
23
25
24
11

**【样例解释 #1】** $1 \oplus (1 + 1) \oplus (1 + 1 + 4) \oplus (1 + 1 + 4 + 5) \oplus (1 + 1 + 4 + 5 + 1) \oplus (1 + 1 + 4 + 5 + 1 + 4) = 18$。 ### 数据规模与约定 **本题采用捆绑测试。** - Subtask 0（13 pts）：保证 $n,q \le 10^2$。 - Subtask 1（28 pts）：保证 $n,q \le 10^4$。 - Subtask 2（19 pts）：保证 $a_i \le 10^4$。 - Subtask 3（7 pts）：保证 $n \le 10^2$。 - Subtask 4（17 pts）：保证 $a_i$ 均为 $2$ 的非负整数次幂。 - Subtask 5（16 pts）：无特殊限制。 对于所有测试数据，$1 \le l \le r \le n \le 10^4$，$1 \le q \le 10^6$，$0 \le a_i \le 10^{10}$。 upd（2024.7.3）：添加一组 hack 数据，减少一组数据。