Bạn đang quản lý một kho lưu trữ hàng hóa và có một danh sách chứa mã số của các sản phẩm trong kho. Nhiệm vụ của bạn là xử lý một số lượng lớn các yêu cầu kiểm tra từ bộ phận quản lý, mỗi yêu cầu yêu cầu bạn tìm một sản phẩm xuất hiện đúng một lần trong một dãy mã sản phẩm con.

Cụ thể, bạn được cung cấp một danh sách gồm \(n\) mã sản phẩm. Bộ phận quản lý sẽ gửi cho bạn \(q\) yêu cầu, mỗi yêu cầu bao gồm hai chỉ số \(l\) và \(r\), yêu cầu bạn kiểm tra các sản phẩm trong khoảng từ \(l\) đến \(r\). Bạn cần tìm một sản phẩm nào đó xuất hiện đúng một lần trong dãy mã sản phẩm này. Nếu có nhiều sản phẩm thỏa mãn, bạn có thể trả lại bất kỳ sản phẩm nào. Nếu không có sản phẩm nào xuất hiện đúng một lần, hãy trả về \(0\).

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(n\) (số lượng mã sản phẩm) và \(q\) (số lượng yêu cầu).
• Dòng thứ hai chứa \(n\) số nguyên, mỗi số là mã của một sản phẩm trong kho.
• \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l\) và \(r\) (yêu cầu tìm sản phẩm trong đoạn từ \(l\) đến \(r\)).

Dữ liệu ra

• Đối với mỗi yêu cầu, in ra mã sản phẩm xuất hiện đúng một lần trong đoạn được yêu cầu. Nếu không có mã sản phẩm nào thỏa mãn, in ra 0.

Điều kiện

• \(1 \le n,q,A_i \le 2 \times 10^5\)
• \(1 \le l,r \le n\)

Input 1

6 2
1 1 2 3 2 4 
2 6
1 2

Output 1

4
0

Input 2

8 7
1 1 2 2 1 1 1 3
1 2
5 5
7 7
4 8
5 5
8 8
1 6

Output 2

0
1
1
3
1
3
0