题目描述
给定一个初始长度为 $n$ 的序列与 $q$ 次操作：操作一，在序列末尾追加整数 $x$；操作二，查询当前序列第 $l$ 到第 $r$ 个元素中第 $k$ 小的值（相同数值按出现次数计）。请用分块加二分等高效方法。
输入格式
第一行两个整数 $n,q$；第二行 $n$ 个整数；接下来 $q$ 行每行形如 1 x 或 2 l r k。
输出格式
对每个操作二输出一行一个整数。
数据范围
$$1 \le n \le 5\times 10^4,\ 1 \le q \le 5\times 10^4,\ |x| \le 10^9$$