题目描述

给定一个元素个数为 $K$ 的数列 $\{a\}$。现规定一个无穷数列 $\{x\}$ 如下：

$$x_i=\begin{cases} a_i, & 1 \le i \le K, \cr \bigoplus_{i=n-1}^{n-K} x_i, & n \ge K \end{cases}$$

给定 $Q$ 组询问 $l_i,r_i$，求 $\bigoplus_{i=l}^r x_i$ 的值。

输入格式

第一行，一个整数 $K$。

第二行，$K$ 个整数 $a_i$。

第三行，一个整数 $Q$。

接下来的 $Q$ 行，每行两个整数 $l_i,r_i$。

输出格式

输出 $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

提示

【数据规模与约定】

• 对于 $100\%$ 的数据，$1 \le K \le 10^5$，$0 \le a_i \lt 10^{18}$，$1 \le Q \le 10^6$，$1 \le l_i \le r_i \le 10^{18}$。

【提示与说明】

题目译自 COCI 2015-2016 #7 Task 3 Ozljeda。

本题分值按 COCI 原题设置，满分 $100$。