시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 64 MB 105 32 25 26.316%

## 문제

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:

• x1 = a1,
• x2 = a2,
• ...
• xk = ak,
• xn = xn−1 ⊕ xn−2 ⊕ ... ⊕ xn−k, 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

• xl ⊕ xl+1 ⊕ ... ⊕ xr−1 ⊕ xr

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.

## 예제 입력 1

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


## 예제 출력 1

3
1
0


## 예제 입력 2

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


## 예제 출력 2

0
4
7
4