D. Судьба
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Как-то раз Леха обнаружил в левом кармане массив состоящий из n целых чисел, а в правом q запросов вида l r k. Если есть запросы, то на них надо ответить. Ответ на запрос — это минимальное x, такое что x встречается на отрезке l r строго больше чем раз или  - 1 если такого числа нет. Помогите Лёхе с таким сложным заданием.

Входные данные

В первой строке содержится два целых числа n и q (1 ≤ n, q ≤ 3·105) — количество элементов в массиве и количество запросов соответственно.

Следующая строка содержит n чисел a1, a2, ..., an (1 ≤ ai ≤ n) — массив Лёхи.

Каждая из следующих q строк содержит по три целых числа l, r и k (1 ≤ l ≤ r ≤ n, 2 ≤ k ≤ 5) — описание запросов.

Выходные данные

Для каждого запроса выведите ответ на него в новой строке.

Примеры
Входные данные
4 2
1 1 2 2
1 3 2
1 4 2
Выходные данные
1
-1
Входные данные
5 3
1 2 1 3 2
2 5 3
1 2 3
5 5 2
Выходные данные
2
1
2