Cho dãy \(A\) gồm \(N\) phần tử là các số nguyên dương \(A_1,A_2,...,A_N\). Nhiệm vụ của bạn là thực hiện \(Q\) truy vấn sau: Tổng \(XOR\) của các giá trị trong phạm vi \([x,y]\) là bao nhiêu?

Input

• Dòng đầu tiên gồm hai số nguyên dương \(N, Q\) là số lượng giá trị và số truy vấn.
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_1,A_2,...,A_N (A_i≤10^9)\).
• \(Q\) dòng tiếp theo, mỗi dòng mô tả một truy vấn, gồm hai số nguyên \(x,y\) \((1≤x≤y≤N)\).

Output

• In ra \(Q\) dòng, mỗi dòng là kết quả của một truy vấn.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N,Q≤2.10^3\).
• Subtask \(2\) (\(50\%\) số điểm): \(N,Q≤2.10^5\).

Example

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

3
0
6
4