Để thử thách tình yêu của mình hôm nay Tina đã cho Luna một mảng có ~N~ chữ số ~a_1, a_2, a_3, \cdots, a_n~. Tina yêu cầu Luna thực hiện ~M~ truy vấn, mỗi truy vấn gồm hai số nguyên ~u, v~ trả lời cho Tina biết giá trị ~a_u \oplus a_{u + 1} \oplus a_{u + 2} \oplus \cdots \oplus a_v~ là bao nhiêu?

Vì quá đam mê vào tình yêu nên Luna không thể làm gì cả, nên anh đã nhờ bạn giúp đỡ trả lời các truy vẫn trên.

Bạn có thể đọc thêm về phép XOR ~(\oplus)~ ở trên tại: https://vnoi.info/wiki/translate/topcoder/fun-with-bits.

Input

Dòng đầu tiên gồm một số nguyên ~N~ ~(1 \leq N \leq 2 * 10^6)~.

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

Dòng thứ ba gồm một số nguyên ~M~ ~(1 \leq M \leq 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 \leq u_i \leq v_i \leq N)~.

Output

Gồm ~M~ dòng là kết quả bài toán.

Simple Input

5
1 2 3 4 5
2
3 5
1 3

Simple Outpt

2
0