撷取密钥

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

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

"咋个找？"CC问。

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

"密码树又是啥子？"

"一种分叉路口。"你蹲下来，在冰晶上画了一棵二叉树的轮廓，"每个数的二进制表示是一条路——遇到0往左拐，遇到1往右拐。查询最大异或和时，从最高位开始，尽量选和当前位相反的方向。"

CC看着那棵树，忽然说："这就像走迷宫，每次都选和当前方向相反的路。"

"对。"

你开始写。先建一棵时间密码树——每个版本插入一个数的二进制路径。查询时，从对应版本的根出发，按位往下走，尽量选和当前位相反的子节点。

屏幕上跳出了结果。最大异或和：47。

"又是47。"CC说。

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

"解码结果。"你说，"Glados说——'47号不是编号，是钥匙。'"

题目描述

$n$ 个数，依次插入。$m$ 个查询，每个查询问第 $i$ 个版本中，$a_j$ 与某个前缀的最大异或值。

输入格式

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

输出格式

每个查询输出最大异或和。

输入样例

3 3
1 2 3
A 4
Q 1 3 0

输出样例

7
7

提示

• 可持久化Trie。每个版本插入一个数的二进制表示。
• 查询时从对应版本的根出发，按位往下走，尽量选相反的子节点。
• 异或值最大 = 按位尽量走相反方向。

第四根时间线，是Echo叛逃前三天。那段时间，Zero已经开始删除她的记忆——不是一次性删除，是碎片化地抹除，像用清除射线慢慢抹掉数据痕迹。

"我要保存剩下的记忆。"Echo说，"把它们按优先级排序——最重要的放在最前面，最不重要放在最后面。"

"咋个排序？"CC问。

"用一种自动平衡的书架。"你说，"每次插入一本新书，书架会自动调整，让左右两边的重量保持平衡。"