Cửa hàng của Bình ghi nhận lượt khách hàng ghé thăm hàng ngày. Khách hàng thứ \(i\) ghé thăm có mã số định danh là \(A_i\).

Để đánh giá mức độ tương tác và lên kế hoạch tri ân, Bình cần trả lời các câu hỏi dạng: "Có bao nhiêu khách hàng khác nhau đã ghé thăm cửa hàng từ lượt thứ \(l\) đến lượt thứ \(r\)?". Do chính sách bảo mật, 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\).

Hãy giúp Bình xây dựng hệ thống xử lý nhanh chóng các truy vấn trê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 dương \(A_1, A_2, \dots, A_N\) (\(1 \le A_i \le 10^9\)) đại diện cho mã số định danh của các lượt khách hàng ghé thăm.
• \(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 số lượng khách hàng khác nhau tìm được trên một dòng riêng biệt.

Ràng buộc & Subtasks

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

Ví dụ

Input:

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

Output:

2
3
3

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, 2, 1]\) có 2 giá trị khác nhau. \(last\_ans = 2\).
• Truy vấn 2: \(l' = 0, r' = 7 \Rightarrow l = 0 \oplus 2 = 2, r = 7 \oplus 2 = 5\). Đoạn \(A[2..5] = [2, 1, 3, 2]\) có 3 giá trị khác nhau. \(last\_ans = 3\).
• Truy vấn 3: \(l' = 0, r' = 6 \Rightarrow l = 0 \oplus 3 = 3, r = 6 \oplus 3 = 5\). Đoạn \(A[3..5] = [1, 3, 2]\) có 3 giá trị khác nhau. \(last\_ans = 3\).