Как-то раз Леха обнаружил в левом кармане массив состоящий из 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
2500 ms 512 Mb Правила оформления программ и список ошибок при автоматической проверке задач