#10000029. 【CSP-S 2024】擂台游戏（arena）

【题目描述】

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

• 第一轮编号为 的选手进行一次对局，编号为 的选手进行一次对局，以此类推，编号为 的选手进行一次对局。

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

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

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

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

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

形式化地，设 是最小的非负整数使得 ，那么应当补充 名选手，且补充的选手的能力值可以任取 之内的整数。如果补充的选手有可能获胜，也应当计入答案中。

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

【输入格式】

从文件 中读入数据。

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

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

输入的第二行包含 个非负整数 ，这列数将用来计算真正的能力值。

输入的第三行包含 个正整数 ，表示询问。

设 是使得 的最小的非负整数，接下来的 行当中，第 行包含 个数（无空格），其中第 个数表示第 轮的第 场比赛抽签得到的 。

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

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

接下来共 行，每行描述一组数据，包含 个非负整数 ，该组数据的能力值 ，其中 。

【输出格式】

输出到文件 中。

共输出 行，对于每组数据，设 为第 （）组询问的答案，你只需要输出一行包含一个整数，表示 的结果。

【样例 输入】

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. 对于长度为 的前缀，由于只有 号一个人，因此答案为 。
2. 对于长度为 的前缀，由于 个人已经是 的幂次，因此不需要进行扩充。根据抽签 可知 号为擂主，由于 ，因此 号获胜，答案为 。
3. 对于长度为 的前缀，首先 号、 号比赛是 号获胜（因为 ，故 号为擂主，），然后虽然 号能力值还不知道，但 号、 号比赛一定是 号获胜（因为 ，故 号为擂主，），而决赛 号、 号谁获胜都有可能（因为 ，故 号为擂主，如果 则 号获胜， 则 号获胜）。综上所述，答案为 。
4. 对于长度为 的前缀，我们根据上一条的分析得知，由于 ，所以决赛获胜的是 号。
5. 对于长度为 的前缀，可以证明，可能获胜的选手包括 号、 号、 号，答案为 。

因此，该组测试数据的答案为 。

【样例 】

见选手目录下的 与 。 这组样例满足特殊性质 。

【样例 】

见选手目录下的 与 。 这组样例满足特殊性质 。

【样例 】

见选手目录下的 与 。

【样例 】

见选手目录下的 与 。

【数据范围】

对于所有测试数据，保证：，，，。

特殊性质 ：保证询问的 均为 的幂次。

特殊性质 ：保证所有的 。