시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 64 MB | 168 | 70 | 55 | 36.667% |
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 nth element in the sequence is denoted with xn. The sequence is defined recursively in the following way:
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
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 1018.
The following line contains the integer Q (1 ≤ Q ≤ 106) from the task.
The ith of the following Q lines contains two integers li and ri (1 ≤ li ≤ ri ≤ 1018) that represent Marin’s ith 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.
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