Дан массив $x_1, x_2, \dots, x_n$. Вам необходимо выполнять два типа запросов к этому массиву:

• Даны $i$ и $y$, присвоить $x_i = y$.
• Дан $l$, найти наименьшее $d$ среди всех кортежей $(a, b, c, d)$, таких что $l \le a < b < c < d$ и $x_a < x_b < x_c < x_d$, или сообщить, что таких кортежей не существует.

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

Первая строка содержит два целых числа $n, q$ ($1 \le n, q \le 500\,000$): количество элементов в массиве и количество запросов. Вторая строка содержит $n$ целых чисел $x_1, x_2, \dots, x_n$ ($1 \le x_i \le 10^9$). Каждая из следующих $q$ строк содержит описание запроса. Если первое число в строке равно 1, то следующие два числа — это $i$ и $y$ ($1 \le i \le n, 1 \le y \le 10^9$), описывающие запрос первого типа. В противном случае первое число в строке равно 2, а следующее число равно $l$ ($1 \le l \le n$), описывающее запрос второго типа.

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

Для каждого запроса второго типа выведите наименьшее $d$ среди всех кортежей $(a, b, c, d)$, таких что $l \le a < b < c < d$ и $x_a < x_b < x_c < x_d$, или выведите «-1», если таких кортежей не существует.

Примеры

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

11 10
1 2 3 4 5 10 9 8 7 6 8
2 1
1 3 2
2 1
1 1 2
2 1
2 5
2 6
1 9 6
1 10 7
2 5

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

4
5
6
-1
-1
11