COCI '15 Contest 7 #3 Ozljeda

View as PDF

Submit solution


Points: 10
Time limit: 1.0s
Memory limit: 64M

Problem types

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{align*}
x_1 &= a_1 \\
x_2 &= a_2 \\
&\ \ \vdots \\
x_k &= a_k \\
x_n &= x_{n-1} \oplus x_{n-2} \oplus \dots \oplus x_{n-k},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 x_l \oplus x_{l+1} \oplus \dots \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 100\,000) 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

Comments

There are no comments at the moment.