给定一个数组 $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