C. Не равный на отрезке
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задан массив из n целых чисел a, а также m запросов. Каждый запрос задан тройкой целых чисел li, ri, xi.

Для каждого запроса вам нужно найти любую позицию pi (li ≤ pi ≤ ri) такую, что api ≠ xi.

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

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

Во второй строке находятся n целых чисел ai (1 ≤ ai ≤ 106) — элементы массива a.

В следующих m строках заданы запросы тремя целыми числами li, ri, xi (1 ≤ li ≤ ri ≤ n, 1 ≤ xi ≤ 106) — параметры i-го запроса.

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

Выведите m строк. На i-й строке выведите целое число pi — позицию любого числа в отрезке [li, ri] не равного xi, либо число  - 1, если такого числа нет.

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