Cho một dãy ~A~ gồm ~N~ số, số thứ ~i~ có giá trị là ~A_i~.

Bạn có ~M~ câu hỏi, câu hỏi thứ ~i~ sẽ có dạng ~(u_i, v_i)~ yêu cầu tìm tổng xor của tất cả các số ~A_j~ mà ~u_i \le j \le v_i~.

Tổng xor của đoạn ~[u_i, v_i]~ được tính theo công thức: ~A_{u_i} \oplus A_{u_i+1} \oplus A_{u_i+2} \oplus \ldots \oplus A_{v_i}~ (~\oplus~ là phép xor).

Đọc thêm về phép xor cũng như các thao tác bit khác tại: https://vnoi.info/wiki/translate/topcoder/fun-with-bits

Dữ liệu

• Dòng đầu tiên gồm một số nguyên ~N~ ~(1 \le N \le 10^5)~.

• Dòng tiếp theo gồm ~N~ số nguyên ~A_i~ ~(1 \le A_i \le 10^9)~.

• Dòng thứ ba gồm một số nguyên ~M~ ~(1 \le M \le 10^5)~.

• ~M~ dòng tiếp theo mỗi dòng gồm hai số nguyên dương ~u_i, v_i~ ~(1 \le u_i \le v_i \le N)~.

Kết quả

• Gồm ~M~ dòng, dòng thứ ~i~ là kết quả của câu hỏi thứ ~i~.

Ví dụ

Sample Input

5
1 2 3 4 5
2
3 5
1 3

Sample Output

2
0

Giải thích

• Ở câu hỏi thứ nhất kết quả là ~3 \oplus 4 \oplus 5 = 2~

• Ở câu hỏi thứ hai kết quả là ~1 \oplus 2 \oplus 3 = 0~

Chấm điểm

• Subtask 1 (50% số test): ~N, M \le 10^3~.

• Subtask 2 (50% số test): ~N, M \le 10^5~.