给你一个数组 $a$。

你需要处理两种类型的询问：

1. 给你 $x$ 和 $y$。将 $a_x$ 设为 $y$。
2. 给你 $l$，$r$ 和 $k$。找到最大的 $m$，使得序列 $k, k + 1, \dots, m$ 是 $a_{l:r}$ 的子序列。

输入格式

第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 10^6$)，分别表示 $a$ 的长度和询问的个数。

第二行包含 $n$ 个整数 $a_i$ ($0 \le a_i < n$)，表示 $a$ 的元素。

接下来的 $q$ 行，每行具有以下格式之一：

• $1\ x\ y$ ($0 \le x, y < n$)，描述第一种类型的询问。
• $2\ l\ r\ k$ ($0 \le l < r \le n, 0 \le k < n$)，描述第二种类型的询问。注意，这里使用的是左闭右开区间，即 $a_{0:3}$ 包含下标为 0、1 和 2 的元素。保证给定的左闭右开区间内至少包含一个等于 $k$ 的元素。

输出格式

对于每个第二种类型的询问，输出对应的 $m$。

样例

输入样例 1

6 17
0 0 0 1 2 1
2 0 4 0
2 0 5 0
1 3 2
2 0 4 0
2 0 6 0
2 0 4 2
2 5 6 1
1 0 1
2 1 6 1
2 0 5 1
1 0 0
1 5 5
1 2 2
1 4 4
1 3 3
1 1 1
2 0 6 0

输出样例 1

1
2
0
1
2
1
1
2
5