P8034 [COCI 2015/2016 #7] Ozljeda

给定一个元素个数为 $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$ 行，每行对应一次询问的答案。

**【数据规模与约定】** - 对于 $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](https://hsin.hr/coci/archive/2015_2016/) [#7](https://hsin.hr/coci/archive/2015_2016/contest7_tasks.pdf) _Task 3 Ozljeda_。** **本题分值按 COCI 原题设置，满分 $100$。**