Truy vấn XOR đoạn (Range Xor Queries)

Nguồn: CSES

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho mảng $n$ số nguyên

Với mỗi truy vấn $[a,b]$, hãy tính phép XOR bit của toàn bộ các phần tử từ vị trí $a$ đến vị trí $b$:

Ký hiệu $\oplus$ biểu diễn phép XOR theo bit.

Input

• Dòng đầu chứa hai số nguyên $n,q$.
• Dòng thứ hai chứa $n$ số nguyên $x_1,x_2,\ldots,x_n$.
• Mỗi trong $q$ dòng tiếp theo chứa hai số nguyên $a,b$.

Output

Với mỗi truy vấn, in trên một dòng giá trị XOR của đoạn $[a,b]$.

Subtask

Điều kiện chung đã đối chiếu với nguồn:

• $1\le n,q\le2\cdot10^5$

• $1\le x_i\le10^9$

• $1\le a\le b\le n$

• Subtask 1 — 20%: $n,q\le40$

• Subtask 2 — 30%: Mọi truy vấn đều có $a=1$.

• Subtask 3 — 50%: không có điều kiện bổ sung ngoài các điều kiện chung ở trê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

Mảng là

• Với $[2,4]$: $2\oplus4\oplus5=3$.
• Với $[5,6]$: $1\oplus1=0$.
• XOR của toàn bộ $8$ phần tử bằng $6$.
• Đoạn $[3,3]$ chỉ có giá trị $4$, nên kết quả là $4$.