Mô tả bài toán:

Cho một mảng gồm ~ n ~ số nguyên, nhiệm vụ của bạn là xử lý ~ q ~ truy vấn dạng: tổng XOR của các giá trị trong đoạn ~[a, b]~ là bao nhiêu?

Input:

• Dòng đầu tiên chứa hai số nguyên ~ n ~ và ~ q ~: số lượng phần tử và số lượng truy vấn.
• Dòng thứ hai chứa ~ n ~ số nguyên ~ x_1, x_2, \ldots, x_n ~: các giá trị trong mảng.
• Tiếp theo có ~ q ~ dòng, mỗi dòng chứa hai số nguyên ~ a ~ và ~ b ~: yêu cầu tính tổng XOR của các phần tử trong đoạn ~[a, b]~.

Output:

• In ra kết quả của mỗi truy vấn.

Ràng buộc:

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

Ví dụ:

Input:

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

Output:

3
0
6
4

Giải thích:

1. Truy vấn 1 (2 4): Tổng XOR của các phần tử trong đoạn ~[2, 4]~ là 2 ^ 4 ^ 5 = 3.
2. Truy vấn 2 (5 6): Tổng XOR của các phần tử trong đoạn ~[5, 6]~ là 1 ^ 1 = 0.
3. Truy vấn 3 (1 8): Tổng XOR của các phần tử trong đoạn ~[1, 8]~ là 3 ^ 2 ^ 4 ^ 5 ^ 1 ^ 1 ^ 5 ^ 3 = 6.
4. Truy vấn 4 (3 3): Tổng XOR của đoạn chỉ chứa 1 phần tử ~[3]~ là 4.