题目描述
给定一个长度为 k 的数列 x1,x2,⋯,xk 作为一个起始值，然后从第 k+1 项开始，无限地延展这个序列，延展后数列 xi 的定义如下：
$$x_i = x_{i-1} \oplus x_{i-2} \oplus \cdots \oplus x_{i-k}
$$
这其中 ⊕ 是将两个数字二进制编码后进行异或操作的意思。
给定 q 个询问，每个询问都带有一组参数 l,r，请计算并输出
xl⊕xl+1⊕⋯⊕xr
的值。
输入格式
第一行：单个整数表示 k；
第二行：k 个整数表示 x1,x2,⋯,xk；
第三行：单个整数表示 q；
第四行到第 q+3 行：每行两个整数 li 与 ri，表示对一个区间的询问。
输出格式
共 q 行：对每个询问，输出一个整数表示答案。
4
1 3 5 7
3
2 2
2 5
1 5
3
1
0
5
3 3 4 3 2
4
1 2
1 3
5 6
7 9
0
4
7
4
数据范围
- 0≤xi≤109；
- 记查询参数 li 与 ri 的最大值为 n。
- 对于 30% 的分数，k≤100，n≤1000，q≤1000；
- 对于 60% 的分数，n≤105；
- 对于 100% 的分数，k≤105，n≤109，q≤105。
