Xorbonacci

Marin swung a racket at flies so hard that he hurt his elbow. His grandmother told him to rub herbs on it and the doctor prescribed a painkiller, but Marin ignored both and went looking for an answer in integer sequences.

He built a new sequence and named it the xorbonacci sequence. Its $n$th term is written $x_n$, and it is defined like this.

• $x_1 = a_1$
• $x_2 = a_2$
• $\dots$
• $x_k = a_k$
• $x_n = x_{n-1} \oplus x_{n-2} \oplus \dots \oplus x_{n-k}$ when $n > k$

Marin says the pain goes away once someone answers his $Q$ queries. Each query gives two numbers $l$ and $r$, and its answer is

$x_l \oplus x_{l+1} \oplus \dots \oplus x_{r-1} \oplus x_r$

Here $\oplus$ is the bitwise XOR operation.

The first line contains the integer $K$ ($1 \le K \le 100\,000$).

The second line contains the first $K$ terms of the xorbonacci sequence. Every value is a nonnegative integer smaller than $10^{18}$.

The third line contains the integer $Q$ ($1 \le Q \le 10^6$).

The $i$th of the next $Q$ lines contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le 10^{18}$) describing the $i$th query.

Print $Q$ lines. The $i$th line holds the answer to the $i$th query of the input.