Cho ~n~ thẻ được xếp theo thứ tự từ ~1~ đến ~n~. Thẻ thứ ~i~ ghi số nguyên ~a_i~.

Để xử lý một đoạn thẻ, bắt đầu với một dãy rỗng ~s~ và lần lượt lấy các thẻ trong đoạn từ trái sang phải. Với mỗi thẻ ghi số ~x~, thực hiện các bước sau.

1. Đặt thẻ mới vào cuối dãy ~s~.
2. Nếu trước thẻ mới đã có một thẻ ghi số ~x~ trong ~s~, xóa cả hai thẻ ghi số ~x~ và tất cả các thẻ nằm giữa chúng. Nếu trước đó chưa có thẻ nào ghi số ~x~, giữ nguyên dãy sau khi thêm.

Sau mỗi bước, các số trên những thẻ còn lại trong ~s~ đôi một khác nhau. Vì vậy, khi thêm một thẻ mới, có nhiều nhất một thẻ cũ cùng số với nó.

Chẳng hạn, khi xử lý đoạn ~[2,1,3,1,2,3]~, dãy ~s~ lần lượt trở thành ~[2]~, ~[2,1]~, ~[2,1,3]~, ~[2]~, ~[]~ và ~[3]~. Kết quả là còn lại một thẻ.

Bạn cần trả lời ~q~ truy vấn theo thứ tự. Với truy vấn thứ ~i~, hãy xử lý các thẻ từ vị trí ~l_i~ đến vị trí ~r_i~, tính cả hai đầu mút, và in ra số thẻ còn lại trong ~s~. Mỗi truy vấn bắt đầu với một dãy ~s~ rỗng.

Hai đầu mút của mỗi truy vấn được mã hóa bằng đáp án của truy vấn ngay trước đó. Gọi đáp án đó là ~\mathrm{lastans}~, với giá trị ban đầu bằng ~0~. Từ cặp số đọc được ~l'_i, r'_i~, giải mã theo công thức

~l_i = l'_i \oplus \mathrm{lastans}, \qquad r_i = r'_i \oplus \mathrm{lastans}.~

Ký hiệu ~\oplus~ là phép XOR theo bit. Sau khi trả lời truy vấn hiện tại, cập nhật ~\mathrm{lastans}~ bằng đáp án vừa tìm được.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ ~(1 \le n,q \le 3 \cdot 10^5)~, lần lượt là số thẻ và số truy vấn.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ ~(1 \le a_i \le n)~.
• Mỗi dòng trong ~q~ dòng tiếp theo chứa hai số nguyên đã mã hóa ~l'_i~ và ~r'_i~ ~(0 \le l'_i,r'_i \le 2n)~.

Đảm bảo sau khi giải mã, mỗi truy vấn thỏa mãn ~1 \le l_i \le r_i \le n~.

Output

In ra ~q~ dòng. Dòng thứ ~i~ chứa số thẻ còn lại sau khi xử lý truy vấn thứ ~i~.

Subtask

Bạn nhận toàn bộ số điểm của một subtask nếu chương trình vượt qua tất cả các test thuộc subtask đó.

Sample Input 1

5 5
3 3 1 1 1
5 5
3 4
3 3
0 5
3 5

Sample Output 1

1
2
1
0
1

Sample Input 2

7 7
2 4 1 2 3 1 2
1 6
0 4
3 3
0 4
0 3
0 6
2 7

Sample Output 2

2
1
1
1
2
3
0

Giải thích

• Ví dụ 1. Các đoạn sau khi giải mã lần lượt là ~[5,5]~, ~[2,5]~, ~[1,1]~, ~[1,4]~ và ~[3,5]~. Chẳng hạn, truy vấn thứ hai được giải mã từ cặp ~(3,4)~ bằng đáp án trước đó là ~1~, cho đoạn ~[2,5]~. Các thẻ của đoạn này mang số ~[3,1,1,1]~. Hai thẻ ~1~ đầu tiên bị xóa khi gặp nhau, nên cuối cùng còn ~[3,1]~.
• Ví dụ 2. Truy vấn cuối có cặp mã hóa ~(2,7)~ và đáp án trước đó bằng ~3~, nên đoạn cần xử lý là ~[1,4]~. Bốn thẻ mang số ~[2,4,1,2]~. Khi thêm thẻ cuối, cả đoạn từ thẻ ~2~ đầu tiên đến thẻ ~2~ vừa thêm bị xóa, nên đáp án bằng ~0~.