Problem E
Ozljeda
Due to the frantical usage of the racket to kill flies, Marin has sustained a serious bodily injury known to the medical community as epicondylitis lateralis humeri. His grandma has advised smearing rakija over it, the doctor has prescribed a strong painkiller, but Marin has ignored every single advice and decided to look for the answer in integer sequences.
He has discovered a previously undiscovered sequence of integers and called it the xorbonacci sequence. The $n$-th element in the sequence is denoted with $x_ n$. The sequence is defined recursively in the following way:
\begin{align*} x_1 & = a_1,\\ x_2 & = a_2,\\ & \ldots \\ x_ k & = a_ k,\\ x_ n & = x_{n-1} \oplus x_{n-2} \oplus \ldots \oplus x_{n-k}, \quad n > k\\ \end{align*}Because of a reason only known to Marin, he determined that all his sorrows will go away if you answer his $Q$ queries defined with numbers $l$ and $r$. The answer to the query is represented with the value
\begin{equation*} x_ l \oplus x_{l+1} \oplus \ldots \oplus x_{r-1} \oplus x_ r \end{equation*}Help Marin and answer his queries.
Please note: The operation $\oplus $ is the operation of binary XOR.
Input
The first line of input contains the integer $K$ ($1 \leq K \leq 100\, 000$) from the task. The following line contains $K$ integers that represent the first $K$ elements in the xorbonacci sequence. All numbers are smaller than $10^{18}$. The following line contains the integer $Q$ ($1 \leq Q \leq 10^6$) from the task. The $i$-th of the following $Q$ lines contains two integers $l_ i$ and $r_ i$ ($1 \leq l_ i \leq r_ i \leq 10^{18}$) that represent Marin’s $i$-th query.
Output
Each of the following $Q$ lines of output must contain the answers to Marin’s queries, the order being the same as the input.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 1 3 5 7 3 2 2 2 5 1 5 |
3 1 0 |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 3 3 4 3 2 4 1 2 1 3 5 6 7 9 |
0 4 7 4 |