Олимпиадный тренинг

Задача . D. Судьба


Задача

Темы: Структуры данных Теория вероятностей *2500

Как-то раз Леха обнаружил в левом кармане массив состоящий из 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) — описание запросов.

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

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


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

time 2500 ms
memory 512 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++5
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет