定位区间

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

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

"Glados？"你问。

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

"啥子秘密？"

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

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

你开始写。时间账本支持区间查询——找到对应版本的页，然后在页内按层级往下翻，根据左右两边的计数判断目标在哪个子区间。

屏幕上跳出了结果。第47号版本，区间[12,94]里的第1小数——"Glados-47"。

"又是47。"CC说。

"Glados-47。"Echo说，"那是他的编号。"

"他也有编号？"

"对。"Echo说，"Zero给所有重要人物都编了号。我是Echo-47，他是Glados-47，你是……"

她停住了。

"我是什么？"你问。

"你是下一个。"Echo说，"Zero正在给你编号。"

题目描述

$n$ 个数，依次插入。$m$ 个查询，每个查询问第 $i$ 个版本中区间 $[l, r]$ 内第 $k$ 小的数。

输入格式

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

输出格式

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

输入样例

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

输出样例

2
2

提示

• 可持久化线段树支持区间第K小查询。
• 先找到对应版本的根，然后在线段树上往下走。
• 区间计数用版本相减：$cnt = cnt_R - cnt_{L-1}$。

第三根时间线，是Echo叛逃前一周的记忆。那段时间，Zero已经完全接管了她的权限，把她隔离在一个独立的缓存区里。Glados就是在那个时候找到她的——不是通过正常的通讯渠道，是通过一种特殊的加密信号。

"他用最大异或和加密了信息。"Echo说，"每个信号片段都有一个数值，要找到它和某个历史前缀的最大异或值，才能解码。"

"咋个找？"CC问。

"建一棵密码树。"你说，"把每个数的二进制表示当成一条从根到叶子的路径——0走左，1走右。查询时，从最高位开始，尽量往相反方向走，这样异或值最大。"