POLSKI SPOJ

Zoologowie przepłynęli rzekę Amazonkę tworząc jednocześnie listę n zwierząt jakie zauważyli po drodze. Każde zwierzę zakwalifikowali do jednego z 500000 gatunków. Chcą oni chronić gatunki zagrożone. Do tego celu potrzebne jest im oprogramowanie, które dla danego przedziału pozycji listy znajdzie dowolny gatunek występujący w nim dokładnie raz.

Wejście

W pierwszej linii wejścia znajdują się dwie liczby całkowite n ∈ [5, 5×10⁵] i q ∈ [1, 5×10⁵] określające odpowiednio liczbę pozycji na liście zwierząt oraz liczbę zapytań.

W drugiej linii wejścia znajduje się n liczb całkowitych z przedziału [1, 5×10⁵] oznaczających gatunki kolejnych zwierząt na liście.

W kolejnych q liniach znajdują się zapytania. Każde zapytania składa się z dwóch liczb całkowitych l, r (1 ≤ l ≤ r ≤ n) określających przedział pozycji listy zwierząt, w którym szukamy niepowtarzającego się gatunku.

Wyjście

Dla każdego zapytania należy w osobnej linii wypisać gatunek, który w danym przedziale występuje dokładnie raz albo 0 jeżeli nie ma takiego gatunku.

Jeżeli dla danego zapytania istnieje wiele rozwiązań, wypisz dowolne z nich.

Przykład

Wejście:

5 4
22 12 12 2018 22
2 3
4 5
5 5
1 4

Wyjście:

0
2018
22
22