题目描述

小 S 想要举办一场擂台游戏，如果共有 $2^k$ 名选手参加，那么游戏分为 $k$ 轮进行： • 第一轮编号为 $1$, $2$ 的选手进行一次对局，编号为 $3$, $4$ 的选手进行一次对局，以此类推，编号为 $2^k − 1$, $2^k$ 的选手进行一次对局。 • 第二轮在只保留第一轮的胜者的前提下，相邻的两位依次进行一场对局。 • 以此类推，第 $k − 1$ 轮在只保留第 $k − 2$ 轮的 $4$ 位胜者的前提下，前两位、后两位分别进行对局，也就是所谓的半决赛。 • 第 $k$ 轮即为半决赛两位胜者的决赛。 确定了游戏晋级的规则后，小 S 将比赛的规则设置为了擂台赛。具体而言，每位选手都有一个能力值 $a_1$, $a_2$, · · · , $a_{2^k}$，能力值为 [$0$, $2^{31} − 1$] 之内的整数。对于每场比赛，会先抽签决定一个数 $0/1$，我们将第 $R$ 轮的第 $G$ 场比赛抽到的数记为 $d_{R,G}$。抽到 $0$ 则表示表示编号小的选手为擂主，抽到 $1$ 则表示编号大的选手为擂主。擂主获胜当且仅当他的能力值 $a ≥ R$。也就是说，游戏的胜负只取决于擂主的能力值与当前比赛是第几轮的大小关系，与另一位的能力值无关 。 现在，小 S 先后陆续收到了 $n$ 位选手的报名信息，他们分别告知了小 S 自己的能力值。小 S 会按照报名的先后顺序对选手进行编号为 $1$, $2$, · · · , $n$。小 S 关心的是，补充尽量少的选手使总人数为 $2$ 的整次幂，且所有选手进行一次完整的擂台游戏后，所有可能成为总冠军的选手的编号之和为多少。 形式化地，设 $k$ 是最小的非负整数使得 $2^k ≥ n$，那么应当补充 ($2^k − n$) 名选手，且补充的选手的能力值可以任取 [$0$, $2^{31} − 1$] 之内的整数。如果补充的选手有可能获胜，也应当计入答案中。 当然小 S 觉得这个问题还是太简单了，所以他给了你 $m$ 个询问 $c_1$, $c_2$, · · · , $c_m$。小S 希望你帮忙对于每个 $c_i$ 求出，在只收到前 $c_i$ 位选手的报名信息时，这个问题的答案是多少。

输入

本题的测试点包含有多组测试数据 ，但不同测试数据只是通过修改 $a_1$, $a_2$, · · · , $a_n$ 得到，其他内容均保持不变，请参考以下格式。其中 ⊕ 代表异或运算符，a\ mod \  b 代表 $a$除以 $b$ 的余数。 输入的第一行包含两个正整数 $n$, $m$，表示报名的选手数量和询问的数量。 输入的第二行包含 $n$ 个非负整数 $a′_1$, $a′_2$, · · · , $a′_n$，这列数将用来计算真正的能力值。 输入的第三行包含 $m$ 个正整数 $c_1$, $c_2$, · · · , $c_m$，表示询问。 设 $K$ 是使得 $2^K ≥ n$ 的最小的非负整数，接下来的 $K$ 行当中，第 $R$ 行包含 $2^{K−R}$个数（无空格），其中第 $G$ 个数表示第 $R$ 轮的第 $G$ 场比赛抽签得到的 $d_{R,G} = 0/1$。 注意，由于询问只是将人数凑齐到 $2^k ≥ c_i$，这里的 $k ≤ K$，因此你未必会用到全部的输入值。 接下来一行包含一个正整数 $T$，表示有 $T$ 组测试数据。 接下来共 $T$ 行，每行描述一组数据，包含 $4$ 个非负整数 $X_0$, $X_1$, $X_2$, $X_3$，该组数据的能力值 $a_i = a′_i ⊕ X_{i\ mod\ 4}$，其中 $1 ≤ i ≤ n$。

输出

共输出 $T$ 行，对于每组数据，设 $A_i$ 为第 $i$（$1 ≤ i ≤ m$）组询问的答案，你只需要输出一行包含一个整数，表示 ($1$ × $A_1$) ⊕ ($2$ × $A_2$) ⊕ · · · ⊕ ($m$ × $A_m$) 的结果。

输入样例

5 5
0 0 0 0 0
5 4 1 2 3
1001
10
1
4
2 1 0 0
1 2 1 0
0 2 3 1
2 2 0 1

输出样例

5
19
7
1

提示

【样例 1 解释】 共有 $T = 4$ 组数据，这里只解释第一组。$5$ 名选手的真实能力值为 [$1$, $0$, $0$, $2$, $1$]。$5$组询问分别是对长度为 $5$, $4$, $1$, $2$, $3$ 的前缀进行的。

1. 对于长度为 $1$ 的前缀，由于只有 $1$ 号一个人，因此答案为 $1$。
2. 对于长度为 $2$ 的前缀，由于 $2$ 个人已经是 $2$ 的幂次，因此不需要进行扩充。根据抽签 $d_{1,1} = 1$ 可知 $2$ 号为擂主，由于 $a_2 < 1$，因此 $1$ 号获胜，答案为 $1$。
3. 对于长度为 $3$ 的前缀，首先 $1$ 号、$2$ 号比赛是 $1$ 号获胜（因为 $d_{1,1} = 1$，故 $2$ 号为擂主，$a_2 < 1$），然后虽然 $4$ 号能力值还不知道，但 $3$ 号、$4$ 号比赛一定是 $4$ 号获胜（因为 $d_{1,2} = 0$，故 $3$ 号为擂主，$a_3 < 1$），而决赛 $1$ 号、$4$ 号谁获胜都有可能（因为 $d_{2,1} = 1$，故 $4$ 号为擂主，如果 $a_4 < 2$ 则 $1$ 号获胜，$a_4 ≥ 2$ 则 $4$ 号获胜）。综上所述，答案为 $1 + 4 = 5$。
4. 对于长度为 $4$ 的前缀，我们根据上一条的分析得知，由于 $a_4 ≥ 2$ ，所以决赛获胜的是 $4$ 号。
5. 对于长度为 $5$ 的前缀，可以证明，可能获胜的选手包括 $4$ 号、$7$ 号、$8$ 号，答案为 $19$。 因此，该组测试数据的答案为 ($1$ × $19$) ⊕ ($2$ × $4$) ⊕ ($3$ × $1$) ⊕ ($4$ × $1$) ⊕ ($5$ × $5$) = $5$。 【数据范围】 对于所有测试数据，保证：$2 ≤ n$,$m ≤ 10^5$，$0 ≤ a_i$, $X_j < 2^{31}$，$1 ≤ c_i ≤ n$，$1 ≤ T ≤ 256$。

测试点	T =	n, m ≤	特殊性质 A	特殊性质 B
1 ∼ 3	1	8	否	否
4, 5		500	是
6 ∼ 8			否	是
9, 10		5, 000		否
11, 12		105	是
13 ∼ 15			否	是
16, 17	4			否
18, 19	16
20, 21	64
22, 23	128
24, 25	256

特殊性质 A：保证询问的 $c_i$ 均为 $2$ 的幂次。 特殊性质 B：保证所有的 $d_{R,G} = 0$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共5个测试点，非原站或官方原始数据。总分100分。