### 问题描述 小秋在学完可持久化线段树之后，他发现如果存在修改操作的话，可持久化线段树就不能做了。因此他想要降低一点难度，并且支持修改操作，题意大概是这样的：给定一个长度为 $n$ 的序列 $a_1 , a_2,a_3 \dots a_n$，需要支持以下三种操作： 1. 令 $a[x] = y$； 2. 在序列 $a$ 的末尾添加一个数 $x$； 3. 输出序列从小到大排序后的第 $k$ 个数。 ### 输入格式 第 $1$ 行输入包含两个整数 $n$ 和 $q$，表示序列 $a$ 最开始的长度和操作次数； 第 $2$ 行输入包含 $n$ 个整数，$a_1 , a_2,a_3 \dots a_n(1 \leq a_i \leq 10^6)$ 表示序列 $a$； 接下来 $q$ 行，输入格式如下： - `1 x y`，表示令 $a[x] = y$，其中 $1 \leq x \leq |a| , 1 \leq y \leq 10^6$，$|a|$ 表示当前序列 $a$ 的长度； - `2 x`，表示在序列 $a$ 的末尾添加一个数 $x( 1 \leq x \leq 10^6)$； - `3 k`，表示输出序列 $a$ 从小到大排序后的第 $k(1\leq k \leq n)$ 个数。 ### 输出格式 对于每次 `3 k` 的操作，输出一行，包含一个整数，表示当前序列从小到大排序后的第 $k$ 个数。 ### 样例输入 ``` 5 5 1 2 3 4 5 1 1 5 2 6 3 5 1 2 3 3 2 ``` ### 样例输出 ``` 5 3 ``` ### 说明 第 $1$ 次操作之后，序列变为 {$5,2,3,4,5$}； 第 $2$ 次操作之后，序列变为 {$5,2,3,4,5,6$}； 第 $3$ 次操作，询问当前序列从小到大第 $5$ 个数是 $5$； 第 $4$ 次操作之后，序列变为 {$5,3,3,4,5,6$}； 第 $5$ 次操作，询问当前序列从小到大第 $2$ 个数是 $3$。 ### 评测数据规模 对于 $20$% 的评测数据，$1 \leq n,q \leq 10^3$； 对于 $40$% 的评测数据，$1\leq n,q \leq 10^4$； 对于 $100$% 的评测数据，$1 \leq n,q \leq 10^5$。