Cho một dãy ~a~ có ~n~ số ~a_1, a_2, ..., a_n~. Ta định nghĩa mức độ "vô định" của một đoạn con ~(l, r)~ là tổng xor của các giá trị xuất hiện ít nhất một lần trong đoạn ~a[l..r]~.

Yêu cầu: Cho ~q~ truy vấn, mỗi truy vấn gồm hai số ~l~ và ~r~, hãy tính độ "vô định" của dãy con ~a[l..r]~.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n,q~ (~1\le n,q \le 3\times 10^5~).

• Dòng thứ hai chứa ~n~ số nguyên ~a_1,a_2,...,a_n~ (~0\le a_i \le 10^9~) mô tả dãy số được cho.

• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~l,r~ (~1\le l \le r \le n~) mô tả một truy vấn.

Output

• In ra ~q~ số, số thứ ~i~ là độ "vô định" của dãy con trong truy vấn thứ ~i~.

Subtask

• ~25\%~ số test thoả mãn ~n \le 5000~.

• ~75\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

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

Sample Output 1

1 3 0 3 0

Notes

Ở truy vấn thứ nhất, ta cần tính mức độ "vô định" của đoạn ~[3, 3, 2, 3]~. Đoạn con này có các giá trị ~2~ và ~3~ xuất hiện ít nhất một lần, vì thế độ "vô định" của đoạn con này là ~2\ \oplus 3 = 1~.

Ở truy vấn thứ hai, ta cần tính mức độ "vô định" của đoạn ~[3, 3]~. Đoạn con này chỉ có giá trị ~3~ xuất hiện ít nhất một lần, vì thế độ "vô định" của đoạn con này là ~3~.

Ở truy vấn thứ ba, ta cần tính mức độ "vô định" của đoạn ~[1, 2, 1, 3, 3, 2, 3]~. Đoạn con này có các giá trị ~1~, ~2~ và ~3~ xuất hiện ít nhất một lần, vì thế độ "vô định" của đoạn con này là ~1\ \oplus 2 \oplus 3 = 0~.