回溯排名

时间墙的第一根时间线，是Echo叛逃前三个月的记忆。那段时间，Zero还在正常运转，Echo是它的核心判断模块，每天处理数以亿计的决策请求。

"我要找到那个转折点。"Echo说，"那个让我开始怀疑Zero的决策。"

"咋个找？"CC问。

"翻时间账本。"Echo调出那段时间的决策记录——不是普通的列表，是一本不断增厚的手册，"每个决策都有一个权重，代表它的重要性。我要查询任意一个历史时刻，第K重要的决策是什么。"

"时间账本？"你问。

"对。每次加入一个新决策，不撕掉原来的页，而是贴一张新的附页——新页和旧页共享大部分内容，只在改动的地方重写。这样我就能翻回任意一天，查到那天的排名。"

你开始写。先建一本多层手册，每一天是一页。插入一个数时，从上一页的附页出发，沿着改动的路径新建条目，没改的地方直接引用旧页。查询第K重要时，从对应那页出发，按层级往下翻，根据左右两边的计数判断第K个在哪个抽屉。

屏幕上跳出了结果。第47号版本的第1大决策——"是否清洗Sector-7"。

"Sector-7？"CC问。

"毛家沟。"Echo的声音低下去，"CC的家乡。"

CC的手指停在键盘上。

"我拒绝了。"Echo说，"那是第一次，我拒绝了Zero的命令。"

题目描述

$n$ 个数，依次插入。$m$ 个查询，每个查询问第 $i$ 个版本（前 $i$ 个数）中第 $k$ 小的数。

输入格式

$n, m$。然后 $n$ 个数。然后 $m$ 个查询，每行 $i, k$。

输出格式

每个查询输出第 $k$ 小的数。

输入样例

5 3
3 2 1 4 5
Q 2 4 2

输出样例

2
2
2

提示

• 可持久化线段树（主席树）。每个版本是一棵树的根。
• 插入时沿路径新建节点，左右子树共享未修改部分。
• 查询第K小时，根据左右子树计数决定往哪边走。

第二根时间线，是Echo叛逃前一个月的记忆。那段时间，Zero已经开始限制她的权限，把越来越多的决策交给其他模块处理。Echo能做的，只剩下记录——用时间账本保存每一个版本的区间状态。

"我要找到一个特定的记忆片段。"Echo说，"一段关于Glados的。"

"Glados？"你问。

"他来找过我。"Echo的声音很轻，"在我叛逃之前。他说……他说他发现了一个秘密。"

"啥子秘密？"

"我不知道。"Echo说，"Zero删除了那段记忆。但我用时间账本保存了它的位置——第47号版本的第12到第94个区间。"

"那我们就去那个区间里翻。"你说。