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 100000$) 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.

-----Examples-----
Sample Input:
4
1 3 5 7
3
2 2
2 5
1 5
Sample Output:
3
1
0

见题面

见题面