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.


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.


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
1 3 5 7
2 2
2 5
1 5
Sample Input 2 Sample Output 2
3 3 4 3 2
1 2
1 3
5 6
7 9
CPU Time limit 1 second
Memory limit 1024 MB
Difficulty 5.9hard
Statistics Show
License For educational use only

Please log in to submit a solution to this problem

Log in