题目描述
给定一个长度为 $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$ 行：对每个询问，输出一个整数表示答案。
样例输入输出
输入#1
复制
4
1 3 5 7
3
2 2
2 5
1 5
输入#2
复制
5
3 3 4 3 2
4
1 2
1 3
5 6
7 9
提示
+ $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$。