配列 $x_1, x_2, \dots, x_n$ が与えられます。 この配列に対して、2種類のクエリを処理する必要があります。

• $i$ と $y$ が与えられたとき、$x_i = y$ と更新する。
• $l$ が与えられたとき、$l \le a < b < c < d$ かつ $x_a < x_b < x_c < x_d$ を満たす組 $(a, b, c, d)$ のうち、$d$ が最小となるものを求める。そのような組が存在しない場合はその旨を報告する。

入力

1行目には、配列の要素数 $n$ とクエリの数 $q$ が与えられます ($1 \le n, q \le 500\,000$)。 2行目には、$n$ 個の整数 $x_1, x_2, \dots, x_n$ が与えられます ($1 \le x_i \le 10^9$)。 続く $q$ 行の各行には、クエリの内容が記述されています。 各行の最初の整数が 1 の場合、続く2つの整数は $i$ と $y$ ($1 \le i \le n, 1 \le y \le 10^9$) であり、第1種のクエリを表します。 それ以外の場合、最初の整数は 2 であり、続く整数は $l$ ($1 \le l \le n$) であり、第2種のクエリを表します。

出力

第2種の各クエリについて、$l \le a < b < c < d$ かつ $x_a < x_b < x_c < x_d$ を満たす組 $(a, b, c, d)$ のうち、$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