Chùm Tín Hiệu Hải Đăng Vũng Tàu

Mô tả

Nhánh hải đăng Vũng Tàu trải dài bờ biển với một chuỗi gồm n trạm phát tín hiệu. Mỗi trạm phát một mã số nguyên dương, đại diện cho cường độ ánh sáng lúc chớp.

Để kiểm tra vùng hoạt động của chùm đèn, kỹ sư vận hành sẽ truy vấn nhiều lần. Mỗi lần, họ chọn một đoạn trạm liên tiếp từ trạm L đến trạm R và muốn biết mã báo cáo tổng hợp của đoạn đó.

Quy tắc gộp báo cáo là dùng phép XOR nhị phân (kí hiệu ^): kết quả bằng XOR của tất cả mã từ trạm L đến trạm R.

Giá trị XOR của một dải số là kết quả khi áp dụng phép toán ^ lên lần lượt các số. Phép ^ trên bit là: giống nhau ra 0, khác nhau ra 1.

Nhiệm vụ: cho mảng mã của các trạm và q truy vấn, với mỗi truy vấn [L, R], in ra XOR tổng hợp của đoạn đó.

Đầu vào

• Dòng đầu: số nguyên n — số lượng trạm (1 ≤ n ≤ 1000).
• Dòng thứ hai: n số nguyên dương, là mã của từng trạm theo thứ tự từ 1 đến n.
• Dòng thứ ba: số nguyên q — số truy vấn (1 ≤ q ≤ 1000).
• q dòng tiếp theo, mỗi dòng hai số nguyên L R (1 ≤ L ≤ R ≤ n).

Đầu ra

• Với mỗi truy vấn, in ra một dòng là XOR tổng hợp đoạn [L, R].

Ràng buộc

• 1 ≤ n, q ≤ 1000.
• 1 ≤ mã mỗi trạm ≤ 10^6.
• Tổng số truy vấn không quá 1000, nên có thể xử lý từng truy vấn trong O(n) nếu muốn, nhưng lời giải khuyên dùng tiền tố XOR để đạt O(1) mỗi truy vấn.

Ví dụ

Input

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

Output

4 7 1

Giải thích:

• Truy vấn [1, 3]: 3 ^ 5 ^ 2. Bit: 3=011, 5=101, 2=010. Lần lượt: 011 ^ 101 = 110, tiếp 110 ^ 010 = 100 = 4. Đáp án: 4.
• Truy vấn [2, 5]: 5 ^ 2 ^ 3 ^ 5. Hai số 5 giống nhau khử nhau (5 ^ 5 = 0), còn lại 0 ^ 2 ^ 3 = 1. Kết quả trung gian: 5^2=7, 7^3=4, 4^5=1. Đáp án: 1.
• Truy vấn [4, 6]: 3 ^ 5 ^ 7. Tính: 3^5=6, 6^7=1. Đáp án: 1.