Tý có một trung tâm giám sát giao thông ghi nhận biển số xe của \(N\) phương tiện đi qua một trạm thu phí theo thứ tự thời gian. Mỗi biển số xe được biểu diễn bằng một số nguyên dương. Cơ quan quản lý muốn thực hiện \(Q\) truy vấn, mỗi truy vấn yêu cầu tìm biển số xe xuất hiện nhiều nhất (tần suất cao nhất) trong khoảng thời gian từ lượt \(L\) đến lượt \(R\). Nếu có nhiều biển số cùng tần suất, hãy in ra biển số nhỏ nhất.

Hãy viết chương trình giúp trung tâm giám sát.

Đị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 thứ hai chứa \(N\) số nguyên dương \(a_1, a_2, \dots, a_N\) — biển số các xe (\(1 \le a_i \le 10^9\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(L, R\) (\(1 \le L \le R \le N\)).

Định dạng đầu ra

• In ra \(Q\) dòng, dòng thứ \(i\) là biển số xe xuất hiện nhiều nhất (nhỏ nhất nếu hòa) trong đoạn \([L, R]\) tương ứng.

Ví dụ

Input:

7 3
1 2 2 3 3 3 4
2 5
1 4
3 7

Output:

2
1
3

Giải thích:

• \([2,5]\): \(\{2,2,3,3\}\) — cả 2 và 3 đều xuất hiện 2 lần, chọn 2.
• \([1,4]\): \(\{1,2,2,3\}\) — 2 xuất hiện 2 lần.
• \([3,7]\): \(\{2,3,3,3,4\}\) — 3 xuất hiện 3 lần.

Subtask