Cho một mảng số nguyên và các truy vấn đoạn [L, R]. Với mỗi truy vấn, hãy tính phép XOR của các phần tử từ vị trí L đến R, kể cả hai đầu mút.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên N, Q.
• Dòng thứ hai chứa N số nguyên A_1, A_2, ..., A_N.
• Mỗi dòng trong Q dòng tiếp theo chứa hai số nguyên L, R.

Dữ liệu ra

Với mỗi truy vấn, in XOR của A_L, A_{L+1}, ..., A_R trên một dòng.

Giới hạn

• 1 ≤ N, Q ≤ 2·10^5.
• 0 ≤ A_i ≤ 10^9.
• 1 ≤ L ≤ R ≤ N.

Ví dụ

Input

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

Output

1
5
3
1