时间限制：1秒　　内存限制：256M

---

题目描述

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

\[x_n=\begin{cases}
a_n, & 1 \le n \le K, \cr
\bigoplus_{i=n-1}^{n-K} x_i, & n > 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\) 行，每行对应一次询问的答案。

输入输出样例 #1

输入 #1

4
1 3 5 7
3
2 2
2 5
1 5

输出 #1

3
1
0

输入输出样例 #2

输入 #2

5
3 3 4 3 2
4
1 2
1 3
5 6
7 9

输出 #2

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}\)。