Xorbonacci

Time limit1sMemory limit64 MB

Summary

Given the first K terms of an XOR recurrence, answer many queries asking for the XOR of terms l through r with indices up to 1e18.

Level: Medium6 of 10
Topics: Math, Prefix sum, Bit manipulation
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Examples2

Example 1
Input
```
4
1 3 5 7
3
2 2
2 5
1 5
```
Expected output
```
3
1
0
```
Example 2
Input
```
5
3 3 4 3 2
4
1 2
1 3
5 6
7 9
```
Expected output
```
0
4
7
4
```