Problem Description

You are given a sequence $\{a\}$ with $K$ elements. Now define an infinite sequence $\{x\}$ as follows:

$$x_n=\begin{cases} a_n, & 1 \le n \le K, \cr \bigoplus_{i=n-1}^{n-K} x_i, & n > K \end{cases}$$

You are given $Q$ queries $(l_i, r_i)$. For each query, find the value of $\bigoplus_{i=l}^r x_i$.

Input Format

The first line contains an integer $K$.

The second line contains $K$ integers $a_i$.

The third line contains an integer $Q$.

The next $Q$ lines each contain two integers $l_i, r_i$.

Output Format

Output $Q$ lines. Each line contains the answer to the corresponding query.

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

3
1
0

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

0
4
7
4

Hint

Constraints

• For $100\%$ of the testdata, $1 \le K \le 10^5$, $0 \le a_i \lt 10^{18}$, $1 \le Q \le 10^6$, $1 \le l_i \le r_i \le 10^{18}$.

Hints and Notes

This problem is translated from COCI 2015-2016 #7 Task 3 Ozljeda.

The score for this problem follows the original COCI settings, with a full score of $100$.

Translated by ChatGPT 5