Cho 1 dãy \(n\) số nguyên, nhiệm vụ của bạn là hãy xử lí \(q\) truy vấn dưới dạng: tính tổng xor của các giá trị trong khoảng [\(a\),\(b\)].

Input

• Dòng đầu tiên gồm hai số nguyên \(n\) và \(q\): số lượng giá trị của dãy và truy vấn
• Dòng thứ hai gồm \(n\) số nguyên \(x_1, x_2,...,x_n\): giá trị dãy số
• Cuối cùng, có \(q\) dòng truy vấn. Mỗi dòng gồm 2 số nguyên \(a\) và \(b\): tính tổng xor của các giá trị trong khoảng [\(a\),\(b\)]

Constraints

• \(1 \leq n,q \leq 2\cdot 10^5\)
• \(1 \leq x_i \leq 10^9\)
• \(1 \leq a \leq b \leq n\)

Output

• In ra kết quả của các truy vấn loại 2

Example

8 4
3 2 4 5 1 1 5 3
2 4
5 6
1 8
3 3

3
0
6
4