Dany jest ciąg $x_1, x_2, \dots, x_n$. Należy wykonać na nim dwa rodzaje zapytań:

• Dla danych $i$ oraz $y$, ustaw $x_i = y$.
• Dla danego $l$, znajdź najmniejsze $d$ spośród wszystkich czwórek $(a, b, c, d)$ spełniających $l \le a < b < c < d$ oraz $x_a < x_b < x_c < x_d$, lub odpowiedz, że takie czwórki nie istnieją.

Wejście

Pierwsza linia zawiera dwie liczby całkowite $n, q$ ($1 \le n, q \le 500\,000$): liczbę elementów w ciągu oraz liczbę zapytań. Druga linia zawiera $n$ liczb całkowitych $x_1, x_2, \dots, x_n$ ($1 \le x_i \le 10^9$). Każda z kolejnych $q$ linii zawiera opis zapytania.

Jeśli pierwsza liczba w linii jest równa 1, to kolejne dwie liczby to $i$ oraz $y$ ($1 \le i \le n, 1 \le y \le 10^9$), opisujące zapytanie pierwszego typu. W przeciwnym razie, pierwsza liczba w linii jest równa 2, a kolejna liczba to $l$ ($1 \le l \le n$), opisująca zapytanie drugiego typu.

Wyjście

Dla każdego zapytania drugiego typu zwróć najmniejsze $d$ spośród wszystkich czwórek $(a, b, c, d)$ takich, że $l \le a < b < c < d$ oraz $x_a < x_b < x_c < x_d$, lub wypisz „-1”, jeśli takie czwórki nie istnieją.

Przykład

Wejście 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

Wyjście 1

4
5
6
-1
-1
11