Due to the frantic 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:

$${\displaystyle \begin{array}{rl}{x}_1& =a_1\\ x_2& =a_2\\ & ⋮\\ x_k& =a_k\\ x_n& =x_{n-1}\oplus x_{n-2}\oplus \cdots \oplus x_{n-k},n>k\end{array}}$$

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 $x_l\oplus x_{l+1}\oplus \cdots \oplus x_{r-1}\oplus x_r$.

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\le K\le 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\le Q\le {10}^6)$ from the task.

The $i^{th}$ of the following $Q$ lines contains two integers $l_i$ and $r_i$ $(1\le l_i\le r_i\le {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

4
1 3 5 7
3
2 2
2 5
1 5

Sample Output 1

3
1
0

Sample Input 2

5
3 3 4 3 2
4
1 2
1 3
5 6
7 9

Sample Output 2

0
4
7
4