编号连续的选手按固定顺序进行二叉淘汰赛：第一轮依次进行 $(1,2),(3,4),\dots$ 的比赛，后续每轮让相邻的胜者配对。

第 $R$ 轮第 $G$ 场比赛的 $d_{R,G}\in\{0,1\}$ 指定擂主：$0$ 表示较小编号者为擂主，$1$ 表示较大编号者为擂主。若擂主的能力值至少为 $R$，则擂主获胜；否则另一位选手获胜，另一位选手的能力值不影响该场结果。

对于每个前缀长度 $c$，保留前 $c$ 位报名选手，并补充到不小于 $c$ 的最小二次幂人数。补充者编号顺延，其能力值可独立任选 $[0,2^{31}-1]$ 中的整数。求在各种补充能力取值下，可能成为冠军的编号之和；每个编号只计一次。抽签 $d$ 固定，不可任选。

输入通过异或生成多组能力值：第 $i$ 人的实际能力为 $a_i\mathbin{\operatorname{XOR}}X_{i\bmod 4}$，其中 $i$ 从 $1$ 开始。

输入格式

第一行包含 $n,m$。第二行包含 $n$ 个初始能力值 $a_i$，第三行包含 $m$ 个前缀查询 $c_i$。

令 $K=\lceil\log_2 n\rceil$。随后给出 $K$ 行：第 $R$ 行是一个长度为 $2^{K-R}$ 的无空格 $01$ 串。再输入一个整数 $T$；接下来 $T$ 行中，第 $t$ 行给出 $X_0,X_1,X_2,X_3$。

输出格式

对每组 $X$ 输出一行。若 $m$ 个查询的答案依次为 $A_1,A_2,\dots,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 \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$。

来源与数据说明

原题页面。以上题意为重新整理的表述，规则、输入输出和约束与原题一致。本题使用独立生成的训练数据，原题测试点表仅说明原比赛范围与特殊性质，本包评分不复刻官方测试点分布。标准输入输出，不要求文件读写。