\begin{problem}{Стёпа и Маша}{стандартный ввод}{стандартный вывод}{3.5 секунд}{64 мегабайта}

Стёпе нравится Маша. А Маше нравится Стёпа. Именно поэтому тёплым весенним деньком Маша и Стёпа решили отправиться в парк на романтическую прогулку. Они беззаботно шли по тропинке, держась за руки, как вдруг подошли к странному спортивному снаряду. Он состоял из $n$ подряд идущих столбиков, расположенных близко друг к другу.

Стёпа быстро оценил высоту каждого из них, и предположил, что высота столбика с номером $i$ равняется $a_i$ метров.

Чтобы произвести впечатление на Машу, Стёпа решил выполнить следующее упражнение: он прыгает на столбик с номером $1$ и затем $k - 1$ раз повторяет следующую процедуру: пусть он стоит на столбике с номером $i$. Тогда прыгает на столбик $j$ с минимальным номером, таким что $j > i$ и $a_{j} > a_{i}$. Проще говоря, он прыгает на ближайший столбик с большим номером и большей высотой. Если же такого столбика нет, Стёпа теряет надежду заполучить сердце Маши, плачет и уходит домой заниматься дифференциальной геометрией.

Стёпа уже выбрал число $k$ и подошел к снаряду, как понял, что катастрофически ошибся. Слабое зрение Стёпы подвело его, и он неправильно оценил высоту некоторых столбиков.

~--- Ничего страшного - подумал Стёпа ~--- и не такое случалось. Если высота этого столбика $16394$ метра, то\ldots

И вдруг Стёпа испугался. Он понял, на какую высоту ему придется залезть и понял, что это слишком опасно.

~--- Я еще так молод ~--- бормотал под нос Стёпа ~--- я впервые влюбился, я только полюбил эту жизнь\ldots И терять её из-за этого снаряда я не готов!

Поэтому Стёпа решил немного уменьшить $k$, чтобы так не рисковать.

Но неудачи, казалось, преследовали Стёпу: он то обнаруживал, что высота столбика неверна, то число $k$ ему казалось неподходящим. Действительно: если он залезет слишком низко, Маша не оценит его способности, а если слишком высоко, есть шанс упасть.

И каждое такое изменение заставляло Стёпу пересчитывать высоту, на которой он в итоге окажется. Казалось, что он будет вечность решать, что же делать, как вдруг Маша крикнула:

~--- Давай быстрее, милый! Я жду!

Больше откладывать выполнение упражнения было нельзя. Напишите программу, которая будет считать, на какой высоте окажется Стёпа после упражнения.

\InputFile
В первой строке входного файла находятся 2 целых числа $(1 \leq n, q \leq 500\,000)$ ~--- количество столбиков и запросов Стёпы, соответственно.

Во второй строке находится $n$ целых чисел $a_i$ $(1 \leq a_i \leq 10^9)$ разделенные пробелами ~--- начальные оценки высот столбиков Стёпой.

Следующие $q$ строк содержат запросы Стёпы. Первое число в строке $t_i$ $(1 \leq t_i \leq 2)$ означает его тип.

Если $t_i = 1$, то далее следуют два числа $p_i$ $x_i$ $(1 \leq p_i \leq n, 1 \leq x_i \leq 10^9)$ - теперь Степа считаю высоту $p_i$ столба равной $x_i$.

Если $t_i = 2$, то далее следуют одно число $k_i$ $(1 \leq k_i \leq n)$ ~--- количество прыжков Стёпы.

\OutputFile
На каждый запрос второго типа выведите высоту на которую заберется Стёпа или `\texttt{-1}' без кавычек, если он не сможет выполнить заданное количество прыжков.

\Example

\begin{example}
\exmp{5 13
1 2 1 3 5
2 1
2 2
2 4
1 1 8
1 3 6
1 2 9
2 1
2 2
2 3
1 5 28
2 3
1 1 333
2 2
}{1
2
5
8
9
-1
28
-1
}%
\end{example}

\end{problem}

