题目描述

       小 $ 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 $ 位选手的报名信息时，这个问题的答案是多少。

输入格式

       从文件 $ arenain $ 中读入数据。
       本题的测试点包含有多组测试数据，但不同测试数据只是通过修改 $ 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 $ 。

输出格式

样例输入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≥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

见选手目录下的 $ 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 ≤ 10^5，0 ≤ a_i , X_j < 2^{31}，1 ≤ c_i ≤ n，1 ≤ T ≤ 256 $ 。