安全系统

题目描述

某安全系统使用一串数字作为加密序列。

系统中共有 n 个数字：

a1 a2 ... an

为了生成不同区间的密码值，系统定义：

对于一个区间 [l,r]，其密码值为该区间内所有数字的异或结果：

$a_l \oplus a_{l+1} \oplus ... \oplus a_r$

其中：

• $\oplus$表示按位异或运算（XOR）。
• 异或运算满足相同数字异或结果为 0。

现在系统需要处理 q 次密码查询。

每次查询给出两个整数：

l r

请输出对应区间 [l,r] 的密码值。

---

输入格式

第一行输入两个整数：

n q

其中：

• n 表示数字序列长度；
• q 表示查询次数。

第二行输入 n 个整数：

a1 a2 ... an

表示加密序列。

接下来 q 行，每行输入两个整数：

l r

表示一次查询的区间范围。

---

输出格式

对于每一次查询，输出一个整数：

表示区间 [l,r] 的密码值。

每个答案占一行。

---

数据范围

1 ≤ n ≤ 100000
1 ≤ q ≤ 100000
0 ≤ a[i] ≤ 100000
1 ≤ l ≤ r ≤ n

---

输入样例

5 3
1 2 3 4 5
1 3
2 5
3 3

---

输出样例

0
0
3

---

样例解释

数字序列：

1 2 3 4 5

---

第一次查询：

1 3

计算：

1 ^ 2 ^ 3

过程：

1 ^ 2 = 3

3 ^ 3 = 0

答案：

0

---

第二次查询：

2 5

计算：

2 ^ 3 ^ 4 ^ 5

过程：

2 ^ 3 = 1

1 ^ 4 = 5

5 ^ 5 = 0

答案：

0

---

第三次查询：

3 3

只有一个数字：

3

答案：

3

---

注意事项

1. 异或运算符为：

^

2. 异或满足：

x ^ x = 0

3. 异或满足交换律：

a ^ b = b ^ a

4. 查询次数较多，不能每次重新计算区间异或。

---

测试点编号	n ≤	q ≤	难度层级	特殊性质	设计目的
1	1	1	弱数据	最小规模、单点查询	检查基本输入输出与 l=r=1
2		3		单元素、多次查询、值为 0	检查 q 循环与零值异或
3	5	4		全 0	所有答案均为 0，卡未初始化或边界错误
4	6	5		小规模递增	便于人工核对，覆盖前缀、后缀、整段
5	7		正常数据	全相同	考察异或的奇偶抵消性质
6	8	6		含 0、重复值、非单调	覆盖重复抵消、零值不影响异或
7				2 的幂与组合值	覆盖不同二进制位的异或
8	6			较大非负 int、含高位	检查高位异或和大数处理
9	30	8		中等规模、交错模式	覆盖跨区间、多段查询
10	50	26		查询较多、单点/前缀/后缀混合	检查大量查询下的稳定性
11	1000	10	极限预备	伪随机、较大 n	覆盖正常大规模与随机分布
12	100000		极限数据	n、q 接近数组上限	卡暴力 O(nq)，验证前缀异或效率