Vous disposez d'un tableau $x_1, x_2, \dots, x_n$. Vous devez effectuer deux types de requêtes sur ce tableau.

• Étant donné $i$ et $y$, définissez $x_i = y$.
• Étant donné $l$, trouvez le plus petit $d$ parmi tous les quadruplets $(a, b, c, d)$ tels que $l \le a < b < c < d$ et $x_a < x_b < x_c < x_d$, ou indiquez qu'il n'existe aucun quadruplet de ce type.

Entrée

La première ligne contient deux entiers $n, q$ ($1 \le n, q \le 500\,000$) : le nombre d'éléments dans le tableau et le nombre de requêtes.

La deuxième ligne contient $n$ entiers $x_1, x_2, \dots, x_n$ ($1 \le x_i \le 10^9$).

Chacune des $q$ lignes suivantes contient la description d'une requête.

Si le premier entier de la ligne est égal à 1, alors les deux entiers suivants sont $i$ et $y$ ($1 \le i \le n, 1 \le y \le 10^9$), décrivant une requête du premier type.

Sinon, le premier entier de la ligne est égal à 2, et l'entier suivant est égal à $l$ ($1 \le l \le n$), décrivant une requête du second type.

Sortie

Pour chaque requête du second type, renvoyez le plus petit $d$ parmi tous les quadruplets $(a, b, c, d)$ tels que $l \le a < b < c < d$ et $x_a < x_b < x_c < x_d$, ou affichez « -1 » s'il n'existe aucun quadruplet de ce type.

Exemples

Entrée 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

Sortie 1

4
5
6
-1
-1
11