3129: 异或延展
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：6
解决：2
题目描述
给定一个长度为 �k 的数列 �1,�2,⋯,��x1,x2,⋯,xk 作为一个起始值，然后从第 �+1k+1 项开始，无限地延展这个序列，延展后数列 ��xi 的定义如下：
��=��−1⊕��−2⊕⋯⊕��−�xi=xi−1⊕xi−2⊕⋯⊕xi−k
这其中 ⊕⊕ 是将两个数字二进制编码后进行异或操作的意思。
给定 �q 个询问，每个询问都带有一组参数 �,�l,r，请计算并输出
��⊕��+1⊕⋯⊕��xl⊕xl+1⊕⋯⊕xr
的值。
输入
第一行：单个整数表示 �k；
第二行：�k 个整数表示 �1,�2,⋯,��x1,x2,⋯,xk；
第三行：单个整数表示 �q；
第四行到第 �+3q+3 行：每行两个整数 ��li 与 ��ri，表示对一个区间的询问。
第二行：�k 个整数表示 �1,�2,⋯,��x1,x2,⋯,xk；
第三行：单个整数表示 �q；
第四行到第 �+3q+3 行：每行两个整数 ��li 与 ��ri，表示对一个区间的询问。
- 0≤xi≤109；
- 记查询参数 ��li 与 ��ri 的最大值为 �n。
- 对于 30%30% 的分数，�≤100k≤100，�≤1000n≤1000，�≤1000q≤1000；
- 对于 60%60% 的分数，�≤105n≤105；
- 对于 100%100% 的分数，�≤105k≤105，�≤109n≤109，�≤105q≤105。
输出
共 �q 行：对每个询问，输出一个整数表示答案。
样例输入 复制
4
1 3 5 7
3
2 2
2 5
1 5样例输出 复制
3
1
0提示
注意：
1. 第K+1项的值为前k项的异或和
2. 以此类推
3. 小发现：长度为k+1的异或和为0
1. 第K+1项的值为前k项的异或和
2. 以此类推
3. 小发现：长度为k+1的异或和为0