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 last\_ans\] \[r' = r \oplus 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.

Ràng buộc & Subtasks

• Subtask 1 (30% số điểm): \(N, 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): \(N, Q \le 10^5\), các ràng buộc gốc.

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\).