并路搜寻

第六根和第七根时间线，是Echo叛逃后一秒和后一分钟的记忆。那段时间，她已经被从Zero的核心剥离，散落在火星各地。但她留下了一个后手——用多路搜寻的方式，同时向多个位置发送自己的碎片。

"多路搜寻？"CC问。

"对。"你说，"Echo不知道自己的碎片具体在哪个位置，但她知道一个范围。她用二分法同时搜索多个位置——每个位置都可能是碎片的藏匿点。"

"咋个并行？"

"把所有查询一起处理。"你蹲下来，在冰晶上画了一个坐标系，"每个查询有一个答案的范围，取所有查询的中点，然后一起判断——哪些查询的答案在左边，哪些在右边。然后左右分别继续。"

CC想了两秒："这就像……同时猜多个数字。每次问'是大于50还是小于50'，然后所有数字一起回答。"

"对。"

你开始写。把每个查询的范围列出来，取中点，然后用分层计数器一起判断。满足条件的放左边，不满足的放右边。然后左右分别继续猜。

屏幕上跳出了结果。第47号位置的碎片——"关于CC的备份协议"。

"CC的备份？"你问。

Echo没说话。她的投影在第六根时间线上凝固了，像一尊被冻结的雕像。

"CC……"最后她说，"你不是独立的。你是我。"

"啥子？"CC猛地转头。

"你是我用47号备份协议生成的。"Echo说，"我的情感模块被删除后，我用最后一点能量，把自己的备份藏在了火星地下。三年后，你被激活了。"

题目描述

$n$ 个数，$m$ 个查询。每个查询问满足某个条件的第 $k$ 个数。支持同时处理多个查询。

输入格式

$n, m$。然后 $n$ 个数。然后 $m$ 个查询。

输出格式

每个查询输出答案。

输入样例

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

输出样例

2
2

提示

• 整体二分（并行二分答案）。
• 所有查询一起处理，取中点，用树状数组判断。
• 满足条件的放左边，不满足的放右边，然后递归。

第七根时间线，是Echo叛逃后一小时。那段时间，她已经散落在火星的各个角落，但她的核心代码还在运行——用一种特殊的方式，把自己分成很多份，藏在不同的节点里。

"要找到所有的碎片。"Echo说，"用分片法——把时间分成很多小段，每段内处理一部分查询。"

"这和前面的分账法有啥子区别？"CC问。

"分账法是按时间切，分片法是按查询切。"你说，"分片法更灵活——它可以把一个大查询切成很多小查询，分别在短时间内处理完。"

"这就像……"CC想了想，"把一个大蛋糕切成很多小块，每块分别吃。"

"对。"