暂无测试数据。

题目描述

小 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

输入 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\) 个人已经是 \(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 \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\)。

测试点	\(T=\)	\(n,m\leq\)	特殊性质 A	特殊性质 B
\(1\sim 3\)	\(1\)	\(8\)	否	否
\(4,5\)	\(1\)	\(500\)	是	否
\(6\sim 8\)	\(1\)	\(500\)	否	是
\(9,10\)	\(1\)	\(5000\)	否	否
\(11,12\)	\(1\)	\(10^5\)	是	否
\(13\sim 15\)	\(1\)	\(10^5\)	否	是
\(16,17\)	\(4\)	\(10^5\)	否	否
\(18,19\)	\(16\)	\(10^5\)	否	否
\(20,21\)	\(64\)	\(10^5\)	否	否
\(22,23\)	\(128\)	\(10^5\)	否	否
\(24,25\)	\(256\)	\(10^5\)	否	否

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

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

限制

时间限制 1.00s

内存限制 512.00MB