异或延展

题目描述

给定一个长度为 $k$ 的数列 $x_1, x_2, \cdots, x_k$ 作为起始值。从第 $k + 1$ 项开始，按照规则 $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$ 的值。

输入格式

1. 第一行：一个整数 $k$ 。
2. 第二行： $k$ 个整数，依次表示 $x_1, x_2, \cdots, x_k$ 。
3. 第三行：一个整数 $q$ 。
4. 第四行到第 $q + 3$ 行：每行两个整数 $l_i$ 与 $r_i$ ，表示一个区间询问。

输出格式

共 $q$ 行，每行输出一个整数，对应每个询问的答案。

数据范围

• $0 \leq x_i \leq 10^9$ 。
• 记查询参数 $l_i$ 与 $r_i$ 的最大值为 $n$ 。
• 对于 30% 的数据， $k \leq 100$ ， $n \leq 1000$ ， $q \leq 1000$ 。
• 对于 60% 的数据， $n \leq 10^5$ 。
• 对于 100% 的数据， $k \leq 10^5$ ， $n \leq 10^9$ ， $q \leq 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