Busy Beaver 有一个包含 $N$ 个正整数的数组 $a_1, \dots, a_N$，其中每个元素均不超过 $N$。他需要对该数组执行 $Q$ 次操作，操作分为以下两种类型：

• $1 \ x \ y$：将 $a_x$ 修改为 $y$。
• $2 \ l \ r$：输出区间 $[1, N]$ 中任意一个未在 $a_l, a_{l+1}, \dots, a_r$ 中出现的整数。

请帮助 Busy Beaver 回答所有的查询！输入数据的生成方式保证对于所有类型 2 的查询，答案一定存在。

输入格式

第一行包含两个正整数 $N$ 和 $Q$ ($2 \le N \le 2 \cdot 10^5$; $1 \le Q \le 2 \cdot 10^5$)。

第二行包含 $N$ 个整数 $a_1, \dots, a_N$ ($1 \le a_i \le N$)。

接下来的 $Q$ 行，每行包含三个正整数，格式为 $1 \ x \ y$ 或 $2 \ l \ r$ ($1 \le x, y \le N$; $1 \le l \le r \le N$)。

输入附加约束：至少包含一个类型 2 的查询，且每个类型 2 的查询都有解。

输出格式

对于每个类型 2 的查询，输出一行包含答案。如果一个查询有多个可能的答案，你可以输出其中任意一个。

子任务

本题共有三个子任务：

• (20 分) $N, Q \le 2000$。
• (30 分) 所有查询均为类型 2。
• (50 分) 无附加约束。

样例

样例输入 1

5 4
3 5 2 1 5
2 1 5
1 4 4
1 3 1
2 3 5

样例输出 1

4
2

说明

在第一次查询中，区间 $[3, 5, 2, 1, 5]$ 中缺失的 $1$ 到 $5$ 之间的唯一整数是 $4$，因此 $4$ 是唯一可能的答案。

第二次查询后，数组变为 $[3, 5, 2, 4, 5]$。

第三次查询后，数组变为 $[3, 5, 1, 4, 5]$。

最后一次查询询问的是区间 $[1, 4, 5]$ 中缺失的 $1$ 到 $5$ 之间的整数。$2$ 或 $3$ 均是该查询的可接受答案。