当前没有测试数据。

本题暂未上传测试数据，目前仅供阅读与练习。

本站练习请使用标准输入/输出；原卷中的文件名仅作原始资料参考。

题目描述

有 $2^k$ 名选手参加一场共 $k$ 轮的淘汰赛。第一轮依次由编号 $1,2$、$3,4$、……、$2^k-1,2^k$ 的选手对局，之后每轮由上一轮剩下的选手按编号顺序相邻两位对局，直到决出冠军。

每位选手有一个 $[0,2^{31}-1]$ 内的整数能力值。第 $R$ 轮第 $G$ 场的抽签值为 $d_{R,G}\in\{0,1\}$：$0$ 表示编号小者为擂主，$1$ 表示编号大者为擂主。擂主获胜当且仅当他的能力值不小于 $R$，与对手的能力值无关；否则对手获胜。

小 S 收到了 $n$ 名选手的报名，按先后顺序编号为 $1,\ldots,n$。对每个询问 $c_i$，只保留前 $c_i$ 名已报名选手，补充尽量少的选手，使总人数为 $2$ 的整次幂。补充选手的能力值可以任取上述范围内的整数。求所有有可能成为冠军的选手编号之和，包含可能获胜的补充选手。

形式化地，令 $k$ 为使 $2^k\ge c_i$ 的最小非负整数，需要补充 $2^k-c_i$ 名选手，编号继续为 $c_i+1,\ldots,2^k$。

输入格式

同一测试点内的多组测试数据仅改变能力值，其余信息保持不变。$\oplus$ 表示按位异或，$a\bmod b$ 表示余数。

第一行两个正整数 $n,m$。第二行 $n$ 个非负整数 $a'_1,\ldots,a'_n$。第三行 $m$ 个询问 $c_1,\ldots,c_m$。

令 $K$ 为使 $2^K\ge n$ 的最小非负整数。接下来 $K$ 行，第 $R$ 行包含 $2^{K-R}$ 个无空格的 $0/1$ 字符，第 $G$ 个字符为 $d_{R,G}$。对于人数较少的询问，未必会用到全部抽签值。

随后一行一个正整数 $T$。接下来 $T$ 行，每行四个非负整数 $X_0,X_1,X_2,X_3$，该组数据的真实能力值为 $a_i=a'_i\oplus X_{i\bmod4}$。

输出格式

输出 $T$ 行。每组数据若各询问的答案为 $A_1,\ldots,A_m$，输出 $(1\times A_1)\oplus(2\times A_2)\oplus\cdots\oplus(m\times A_m)$。

样例 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

输出

5
19
7
1

数据范围

$2\le n,m\le10^5$，$0\le a_i,X_j<2^{31}$，$1\le c_i\le n$，$1\le T\le256$。

原卷完整题面

以下保留原卷的图示、完整样例解释、分档约束和特殊性质，便于核对。原卷中引用的外部样例文件未随本次题面上传。

下载原卷题面 PDF