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

• 第一轮编号为 1, 2 的选手进行一次对局，编号为 3, 4 的选手进行一次对局，以此类推，编号为 2^k - 1, 2^k 的选手进行一次对局。
• 第二轮在只保留第一轮的胜者的前提下，相邻的两位依次进行一场对局。
• 以此类推，第 k - 1 轮在只保留第 k - 2 轮的 4 位胜者的前提下，前两位、后两位分别进行对局，也就是所谓的半决赛。
• 第 k 轮即为半决赛两位胜者的决赛。

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

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

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

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

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

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

输入的第二行包含 n 个非负整数 a'_1,a'_2,\dots,a'_n，这列数将用来计算真正的能力值。

输入的第三行包含 m 个正整数 c_1, c_2, \dots , c_m，表示询问。

设 K 是使得 2^K \geq n 的最小的非负整数，接下来的 K 行当中，第 R 行包含 2^{K-R} 个数（无空格），其中第 G 个数表示第 R 轮的第 G 场比赛抽签得到的 d_{R,G}=0/1。

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

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

接下来共 T 行，每行描述一组数据，包含 4 个非负整数 X_0,X_1,X_2,X_3，该组数据的能力值 a_i=a'_i \oplus X_{i\bmod 4}，其中 1\leq i\leq n。

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

【样例 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 \geq 2 则 4 号获胜）。综上所述，答案为 1 + 4 = 5。
4. 对于长度为 4 的前缀，我们根据上一条的分析得知，由于 a_4 \geq 2 ，所以决赛获胜的是 4 号。
5. 对于长度为 5 的前缀，可以证明，可能获胜的选手包括 4 号、7 号、8 号，答案为 19。

因此，该组测试数据的答案为 (1 \times 19) \oplus (2 \times 4) \oplus (3 \times 1) \oplus (4 \times 1) \oplus (5 \times 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 \leq n, m \leq 10^5，0 \leq a_i, X_j < 2^{31}，1 \leq c_i \leq n，1 \leq T \leq 256。

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

特殊性质 B：保证所有的 d_{R,G} = 0。

CSP-S 2024

CSP-S 2024