题目描述

给定一个长度为 $n$ 的数列 $a_1,a_2,\ldots,a_n$。有 $q$ 次操作：

• 1 x y：将 $a_x$ 修改为 $y$。
• 2 k：查询全局第 $k$ 小。

输入格式

第一行输入 $n,q$。

第二行输入 $a_1,a_2,\ldots,a_n$。

接下来 $q$ 行，每行输入格式如题目描述所示。

输出格式

输出一共输出若干行，针对操作 $2$ 输出一个整数代表答案。

5 3
1 3 11 13 20
2 3
1 3 5
2 3

11
5

数据规模与约定

• 对于 $50\%$ 的数据，$1 \le n,q \le 2\cdot 10^3$。

• 对于 $100\%$ 的数据，$1 \le n,q \le 5\cdot 10^5$。

其余所有数字 $\leq 2\cdot 10^6$。