P8034 [COCI 2015/2016 #7] Injury (Ozljeda)

You are given a sequence $\{a\}$ with $K$ elements. Now define an infinite sequence $\{x\}$ as follows: $$x_n=\begin{cases} a_n, & 1 \le n \le K, \cr \bigoplus_{i=n-1}^{n-K} x_i, & n > K \end{cases}$$ You are given $Q$ queries $(l_i, r_i)$. For each query, find the value of $\bigoplus_{i=l}^r x_i$.

The first line contains an integer $K$. The second line contains $K$ integers $a_i$. The third line contains an integer $Q$. The next $Q$ lines each contain two integers $l_i, r_i$.

Output $Q$ lines. Each line contains the answer to the corresponding query.

**Constraints** - For $100\%$ of the testdata, $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}$. **Hints and Notes** **This problem is translated from [COCI 2015-2016](https://hsin.hr/coci/archive/2015_2016/) [#7](https://hsin.hr/coci/archive/2015_2016/contest7_tasks.pdf) _Task 3 Ozljeda_.** **The score for this problem follows the original COCI settings, with a full score of $100$.** Translated by ChatGPT 5