题目背景

小 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 数据，减少一组数据。