题目描述

小 S 要举办一场擂台游戏。当共有 $2^k$ 名选手时，比赛共进行 $k$ 轮：第一轮由编号 $1,2$ 的选手对局，编号 $3,4$ 的选手对局，依此类推；以后每轮由上一轮相邻两场的胜者进行对局，直至决出冠军。

第 $i$ 名选手的能力值为 $a_i$。第 $R$ 轮第 $G$ 场比赛的抽签结果记为 $d_{R,G}\in\{0,1\}$：

• $d_{R,G}=0$ 时，编号较小的选手是擂主；
• $d_{R,G}=1$ 时，编号较大的选手是擂主。

擂主获胜当且仅当其能力值 $a\ge R$；否则另一名选手获胜。比赛结果只取决于擂主的能力值和当前轮数。

小 S 按报名顺序收到 $n$ 名选手的信息，并依次编号为 $1,2,\ldots,n$。对于只有前 $c$ 名选手报名的情况，设 $k$ 为满足 $2^k\ge c$ 的最小非负整数，需要再补充 $2^k-c$ 名选手。补充选手的能力值可以在 $[0,2^{31}-1]$ 内任意选择。如果某位补充选手在某种能力值选择下能够成为冠军，也要计入可能的冠军。

对于每次询问 $c_i$，求所有可能成为冠军的选手编号之和，记为 $A_i$。

本题包含 $T$ 组数据。各组数据仅通过异或改变选手能力值，其余输入均相同。对于每组数据，只需输出所有询问答案按题目规定异或后的结果。

输入格式

本题原题采用文件读写，输入文件名为 arena.in，输出文件名为 arena.out。在 Hydro 上提交时，使用标准输入输出即可。

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

第二行包含 $n$ 个非负整数 $a'_1,a'_2,\ldots,a'_n$，用于生成各组数据中的真实能力值。

第三行包含 $m$ 个正整数 $c_1,c_2,\ldots,c_m$，表示各次询问的报名人数。

设 $K$ 为满足 $2^K\ge n$ 的最小非负整数。接下来 $K$ 行中，第 $R$ 行包含一个长度为 $2^{K-R}$ 的二进制字符串，第 $G$ 个字符表示 $d_{R,G}$。字符之间没有空格。

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

接下来 $T$ 行，每行包含四个非负整数 $X_0,X_1,X_2,X_3$。该组数据中，第 $i$ 名选手的真实能力值为

$a_i=a'_i\oplus X_{i\bmod 4}$，

其中 $\oplus$ 表示按位异或。

输出格式

输出 $T$ 行。对于每组数据，设第 $i$ 次询问的答案为 $A_i$，输出

$(1\times A_1)\oplus (2\times A_2)\oplus \cdots \oplus (m\times A_m)$。

样例

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

来源

CSP-S 2024 第 4 题

数据范围与提示

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

• $2 \le n,m \le 10^5$。
• $0 \le a'_i,X_j < 2^{31}$。
• $1 \le c_i \le n$。
• $1 \le T \le 256$。

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

• 特殊性质 A：所有询问的 $c_i$ 均为 $2$ 的幂。
• 特殊性质 B：所有 $d_{R,G}=0$。