异或延展

题目描述

给定一个长度为 $k$ 的数列 $x_1, x_2, \cdots, x_k$ 作为一个起始值，然后从第 $k+1$ 项开始，无限地延展这个序列，延展后数列 $x_i$ 的定义如下：

$$x_i = x_{i-1} \oplus x_{i-2} \oplus \cdots \oplus x_{i-k}$$

其中 $\oplus$ 是将两个数字二进制编码后进行异或操作。

给定 $q$ 个询问，每个询问带有参数 $l, r$，请计算并输出

$$x_l \oplus x_{l+1} \oplus \cdots \oplus x_r$$

的值。

输入格式

第一行：单个整数表示 $k$； 第二行：$k$ 个整数表示 $x_1, x_2, \cdots, x_k$； 第三行：单个整数表示 $q$； 第四行到第 $q+3$ 行：每行两个整数 $l_i$ 与 $r_i$。

输出格式

共 $q$ 行：对每个询问，输出一个整数表示答案。

数据范围

$0 \le x_i \le 10^9$；记查询参数 $l_i$ 与 $r_i$ 的最大值为 $n$。 对于 30% 的分数，$k \le 100, n \le 1000, q \le 1000$； 对于 60% 的分数，$n \le 10^5$； 对于 100% 的分数，$k \le 10^5, n \le 10^9, q \le 10^5$。

样例输入 #1

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

样例输出 #1

3
1
0

样例输入 #2

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

样例输出 #2

0
4
7
4

知识点与难度

本题涉及的知识点从属于 GESP五级（递推、位运算、找规律），难度等级：⭐⭐⭐⭐。

---

测试点分布

Subtask	分值	测试点编号	说明
0	10	1~2	样例
1	20	3~8	小规模
2	15	9~11	Hack
3	30	12~20	中大规模
4	25	21~25	随机回归