Виртуальное соревнование – это способ прорешать прошедшее соревнование в режиме, максимально близком к участию во время его проведения. Поддерживается только ICPC режим для виртуальных соревнований.
Если вы раньше видели эти задачи,
виртуальное соревнование не для вас – решайте эти задачи в архиве.
Если вы хотите просто дорешать задачи, виртуальное соревнование не для вас – решайте эти задачи в архиве.
Запрещается использовать чужой код, читать разборы задач и общаться по содержанию соревнования с кем-либо.
Вам задан массив из 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, если такого числа нет.