\(7^{th}\) round, March \(5^{th}\) 2016
Due to the frantical 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:
\(x@@RISE_MATH_BLOCK_0@@n = x@@RISE_MATH_BLOCK_1@@n - 2\) ⊕... ⊕\(x_{n}\){−}, \(n > k\)
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}\) ⊕\(x_{l}\)_{+1} ⊕... ⊕\(x@@RISE_MATH_BLOCK_2@@r\)
Help Marin and answer his queries.
Please note: The operation ⊕is the operation of binary XOR.

The first line of input contains the integer \(K\) (1 ⩽\(K\) ⩽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 ⩽\(Q\) ⩽\(10^{6}\)) from the task.
The \(i\)^{th} of the following \(Q\) lines contains two integers \(l_{i}\) and \(r_{i}\) (1 ⩽\(l_{i}\) ⩽\(r_{i}\) ⩽\(10^{18}\)) that represent
Marin’s \(i\)^{th} query.

Each of the following \(Q\) lines of output must contain the answers to Marin’s queries, the order being
the same as the input.

생성자가 기록되지 않았습니다.

출처 COCI 2015/2016 Contest 7