給定一個陣列 $x_1, x_2, \dots, x_n$。 你需要對此陣列執行兩種類型的查詢：

• 給定 $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$，若不存在這樣的四元組，則回覆無解。

輸入格式

第一行包含兩個整數 $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$)，描述第二種類型的查詢。

輸出格式

對於每個第二種類型的查詢，回傳滿足 $l \le a < b < c < d$ 且 $x_a < x_b < x_c < x_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