Se te da un arreglo $x_1, x_2, \dots, x_n$. Debes realizar dos tipos de consultas sobre este arreglo:

• Dados $i$ y $y$, establece $x_i = y$.
• Dado $l$, encuentra el $d$ más pequeño entre todas las tuplas $(a, b, c, d)$ con $l \le a < b < c < d$ y $x_a < x_b < x_c < x_d$, o responde que no existen tales tuplas.

Entrada

La primera línea contiene dos enteros $n, q$ ($1 \le n, q \le 500\,000$): el número de elementos en el arreglo y el número de consultas.

La segunda línea contiene $n$ enteros $x_1, x_2, \dots, x_n$ ($1 \le x_i \le 10^9$).

Cada una de las siguientes $q$ líneas contiene la descripción de una consulta.

Si el primer entero en la línea es igual a 1, entonces los siguientes dos enteros son $i$ y $y$ ($1 \le i \le n$, $1 \le y \le 10^9$), describiendo una consulta del primer tipo.

De lo contrario, el primer entero en la línea es igual a 2, y el siguiente entero es igual a $l$ ($1 \le l \le n$), describiendo una consulta del segundo tipo.

Salida

Para cada consulta del segundo tipo, devuelve el $d$ más pequeño entre todas las tuplas $(a, b, c, d)$ tales que $l \le a < b < c < d$ y $x_a < x_b < x_c < x_d$, o imprime "-1" si no existen tales tuplas.

Ejemplos

Entrada 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

Salida 1

4
5
6
-1
-1
11