Dãy số Xorbonacci

Dãy số Xorbonacci với phần tử thứ ~n~ ký hiệu ~x_n~ và được định nghĩa đệ quy như sau:

$$\displaystyle \begin{align} x_1 &= a_1 \\ x_2 &= a_2 \\ \ldots \\ x_k &= a_k \\ x_n &= x_{n-1} \oplus x_{n-2} \oplus x_{n-3} \oplus x_{n-4} \ldots \oplus x_{n-k}, n> k \end{align}$$

Bài toán hôm nay Trung dành cho các bạn là tính giúp giá trị: ~x_l \oplus x_{l+1} \oplus x_{l+2} \ldots \oplus x_r~ với hai giá trị ~l, r~ cho trước. Phép toán ký hiệu ~\oplus~ là phép xor nhị phân.

Input

Dòng thứ nhất là số nguyên ~K~ thỏa ~1 \le K \le 10^5~.

Dòng thứ hai chứa ~K~ số nguyên đầu tiên của dãy số ~a_i~ thỏa ~1 \le a_i \le 10^{18}~.

Dòng số ba chứa số nguyên ~Q~ là số câu hỏi cần hỏi thỏa ~1 \le Q \le 10^6~.

~Q~ dòng tiếp theo mỗi dòng chứa hai số nguyên ~l_i, r_i~ là phạm vi cần hỏi cho công thức cần tính giá trị thỏa ~1 \le l_i \le r_i \le 10^{18}~.

Output

Ứng với mỗi câu hỏi in giá trị cần tính, mỗi giá trị in trên một dòng.

Samples

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