Cho dãy \(A\) gồm N số nguyên không âm. Nhiệm vụ của bạn là lập trình giải quyết bài toán tìm số nguyên không âm nhỏ nhất không xuất hiện trong đoạn con từ chỉ số l đến r (giá trị này được gọi là MEX của đoạn con \(A[l..r]\)).

Vì tính chất bảo mật và tránh các thuật toán ngoại tuyến (offline), các câu hỏi được mã hóa online như sau: \(l' = l \oplus \text{last\_ans}\), \(r' = r \oplus \text{last\_ans}\) Trong đó \(last\_ans\) là kết quả của truy vấn trước đó (\(ban đầu last\_ans = 0\)). Hệ thống chỉ chấp nhận câu hỏi nếu sau khi giải mã thỏa mãn \(1 \le l \le r \le N\).

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên dương \(N\) và Q (\(1 \le N, Q \le 10^5\)).
• Dòng hai chứa \(N\) số nguyên không âm \(A_1, A_2, \dots, A_N\) (\(0 \le A_i \le 10^9\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l'\) và \(r'\) là truy vấn đã được mã hóa.

Định dạng đầu ra

• Với mỗi truy vấn hợp lệ, in ra giá trị MEX tìm được trên một dòng riêng biệt.

Ví dụ

Input:

5 3
1 0 2 0 1
1 3
0 7
0 3

Output:

3
1
2

Giải thích:

• Ban đầu \(last\_ans = 0\).
• Truy vấn 1: \(l' = 1, r' = 3 \Rightarrow l = 1 \oplus 0 = 1, r = 3 \oplus 0 = 3\). Đoạn \(A[1..3] = [1, 0, 2]\) có MEX là 3. \(last\_ans = 3\).
• Truy vấn 2: \(l' = 0, r' = 7 \Rightarrow l = 0 \oplus 3 = 3, r = 7 \oplus 3 = 4\). Đoạn \(A[3..4] = [2, 0]\) có MEX là 1. \(last\_ans = 1\).
• Truy vấn 3: \(l' = 0, r' = 3 \Rightarrow l = 0 \oplus 1 = 1, r = 3 \oplus 1 = 2\). Đoạn \(A[1..2] = [1, 0]\) có MEX là 2. \(last\_ans = 2\).

Ràng buộc & Subtasks

• **Subtask 1 (30% số điểm):\(Q \le 1000\).
• **Subtask 2 (30% số điểm):\(A_i \le 20 v ới mọi 1 \le i \le N\).
• **Subtask 3 (40% số điểm):\(Q \le 10^{5}, các ràng buộc gốc\).