擂台游戏(arena)

题目描述

小 S 想要举办一场擂台游戏，如果共有 2k 名选手参加，那么游戏分为 k 轮进行:

第一轮编号为 1, 2 的选手进行一次对局，编号为 3, 4 的选手进行一次对局，以此

类推，编号为 2k − 1, 2k 的选手进行一次对局。

第二轮在只保留第一轮的胜者的前提下，相邻的两位依次进行一场对局。

以此类推，第 k − 1 轮在只保留第 k − 2 轮的 4 位胜者的前提下，前两位、后两位分别进行对局,也就是所谓的半决赛。

第 k 轮即为半决赛两位胜者的决赛。

确定了游戏晋级的规则后，小 S 将比赛的规则设置为了擂台赛。具体而言，每位选 手都有一个能力值 a1 , a2 , · · · , a2k ，能力值为 [0, 231 − 1] 之内的整数。对于每场比赛，会 先抽签决定一个数 0/1，我们将第 R 轮的第 G 场比赛抽到的数记为 dR,G。抽到 0 则表 示表示编号小的选手为擂主，抽到 1 则表示编号大的选手为擂主。擂主获胜当且仅当他 的能力值 a ≥ R。也就是说，游戏的胜负只取决于擂主的能力值与当前比赛是第几轮的 大小关系，与另一位的能力值无关。

现在，小 S 先后陆续收到了 n 位选手的报名信息，他们分别告知了小 S 自己的能 力值。小 S 会按照报名的先后顺序对选手进行编号为 1, 2, · · · , n。小 S 关心的是，补充 尽量少的选手使总人数为 2 的整次幂，且所有选手进行一次完整的擂台游戏后，所有可 能成为总冠军的选手的编号之和为多少。

形式化地，设 k 是最小的非负整数使得 2k ≥ n，那么应当补充 (2k − n) 名选手，且 补充的选手的能力值可以任取[0,231−1]之内的整数。如.果.补.充.的.选.手.有.可.能.获.胜.，也应当计入答案中。

当然小 S 觉得这个问题还是太简单了，所以他给了你 m 个询问 c1, c2, · · · , cm。小 S 希望你帮忙对于每个 ci 求出，在只收到前 ci 位选手的报名信息时，这个问题的答案 是多少。

输入格式

从文件 arena.in 中读入数据。

本题的测试点包含有多组测试数据.，但不同测试数据只是通过修改a1,a2,··· ,an 得 到，其他内容均保持不变，请参考以下格式。其中 ⊕ 代表异或运算符，a mod b 代表 a 除以 b 的余数。

输入的第一行包含两个正整数 n, m，表示报名的选手数量和询问的数量。

输入的第二行包含 n 个非负整数 a′1, a′2, · · · , a′n，这列数将用来计算真正的能力值。 

输入的第三行包含 m 个正整数 c1, c2, · · · , cm，表示询问。

设K是使得2K ≥n的最小的非负整数，接下来的K行当中，第R行包含2K−R个数(无空格)，其中第 G 个数表示第 R 轮的第 G 场比赛抽签得到的 dR,G = 0/1。

注意，由于询问只是将人数凑齐到 2k ≥ ci，这里的 k ≤ K，因此你未必会用到全部 的输入值。

接下来一行包含一个正整数 T，表示有 T 组测试数据。

接下来共 T 行，每行描述一组数据，包含 4 个非负整数 X0, X1, X2, X3，该组数据 的能力值ai =a′i ⊕Ximod4，其中1≤i≤n。

输出格式

输出到文件 arena.out 中。

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

样例 1 输入

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

样例 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 的幂次，因此不需要进行扩充。根据 抽签d1,1 = 1可知2号为擂主，由于a2 < 1，因此1号获胜，答案为1。

对于长度为 3 的前缀，首先 1 号、2 号比赛是 1 号获胜(因为 d1,1 = 1，故 2 号 为擂主，a2 < 1)，然后虽然 4 号能力值还不知道，但 3 号、4 号比赛一定是 4 号 获胜(因为 d1,2 = 0，故 3 号为擂主，a3 < 1)，而决赛 1 号、4 号谁获胜都有可 能(因为d2,1 = 1，故4号为擂主，如果a4 < 2则1号获胜，a4 ≥ 2则4号获 胜)。综上所述，答案为 1 + 4 = 5。

对于长度为 4 的前缀，我们根据上一条的分析得知，由于 a4 ≥ 2 ，所以决赛获 胜的是4 号。

对于长度为 5 的前缀，可以证明，可能获胜的选手包括 4 号、7 号、8 号，答案 为 19。

因此，该组测试数据的答案为(1×19)⊕(2×4)⊕(3×1)⊕(4×1)⊕(5×5) = 5。 

样例 2

见选手目录下的 arena/arena2.in 与 arena/arena2.ans。 这组样例满足特殊性质 A。

样例 3

见选手目录下的 arena/arena3.in 与 arena/arena3.ans。

这组样例满足特殊性质 B。 

样例 4

见选手目录下的 arena/arena4.in 与 arena/arena4.ans。 

样例 5

见选手目录下的 arena/arena5.in 与 arena/arena5.ans。 

数据范围

对于所有测试数据，保证:2 ≤ n,m ≤ 105，0 ≤ ai,Xj < 231，1 ≤ ci ≤ n，1 ≤ T ≤ 256。

特殊性质 A:保证询问的 ci 均为 2 的幂次。

特殊性质 B:保证所有的 dR,G = 0。