时间限制： 1.0 秒

空间限制： 256 MB

问题描述

创造一个世界只需要定义一个初状态和状态转移规则。

宏观世界的物体运动规律始终跟物体当前的状态有关，也就是说只要知道物体足够多的状态信息，例如位置、速度等，我们就能知道物体之后任意时刻的状态。

现在小 M 创造了一个简化的世界。

这个世界中，时间是离散的，物理规律是线性的：世界的初始状态可以用一个 $m$ 维向量 $b^{(0)}$ 表示，状态的转移方式用 $m \times m$ 的矩阵 $A$ 表示。

若已知这个世界当前的状态是 $b$，那么下一时刻就等于 $b$ 左乘状态转移矩阵 $A$，即 $Ab$。

这个世界中，物体的状态也是离散的，也就是说可以用整数表示。再进一步，整数都可以用二进制编码拆分为有限位 $0$ 和 $1$。因此，这里的矩阵 $A$ 和向量 $b$ 的每个元素都是 $0$ 或 $1$，矩阵乘法中的加法运算视为异或运算（$\mathrm{xor}$），乘法运算视为与运算（$\mathrm{and}$）。

具体地，设矩阵 $A$ 第 $i$ 行第 $j$ 列的元素为 $a_{i, j}$，向量 $b$ 的第 $i$ 个元素为 $b_i$。那么乘法 $Ab$ 所得的第 $k$ 个元素为

$$(a_{k,1}\text{ and }b_1)\text{ xor }(a_{k,2}\text{ and }b_2)\text{ xor } \cdots\text{ xor }(a_{k,m}\text{ and }b_m) $$

矩阵和矩阵的乘法也有类似的表达。

小 M 发现，这样的矩阵运算也有乘法结合律，例如有 $A(Ab) = (AA)b = A^2b$。

为了保证自己创造的世界维度不轻易下降，小 M 保证了矩阵 $A$ 可逆，也就是说存在一个矩阵 $A^{-1}$，使得对任意向量 $d$，都有 $A^{-1}Ad=d$。

小 M 想了解自己创造的世界是否合理，他希望知道这个世界在不同时刻的状态。

具体地，小 M 有 $n$ 组询问，每组询问会给出一个非负整数 $k$，小 M 希望你帮他求出 $A^kb$。

输入格式

从标准输入读入数据。

输入第一行包含一个整数 $m$，表示矩阵和向量的规模。

接下来 $m$ 行，每行包含一个长度为 $m$ 的 $01$ 串，表示矩阵 $A$。

接下来一行，包含一个长度为 $m$ 的 $01$ 串，表示初始向量 $b^{(0)}$。（$b^{(0)}$ 是列向量，这里表示它的转置）

注意：$01$ 串两个相邻的数字之间均没有空格。

接下来一行，包含一个正整数 $n$，表示询问的个数。

最后 $n$ 行，每行包含一个非负整数 $k$，表示询问 $A^kb(0)$。

注意：$k$ 可能为 $0$，此时是求 $A^0b^{(0)} = b^{(0)}$。

输出格式

输出到标准输出。

输出 $n$ 行，每行包含一个 $01$ 串，表示对应询问中 $A^kb^{(0)}$ 的结果。

注意：$01$ 串两个相邻的数字之间不要输出空格。

3
110
011
111
101
10
0
2
3
14
1
1325
6
124124
151
12312

101
010
111
101
110
010
100
101
001
100

评测用例规模与约定

本题使用 $10$ 个评测用例来测试你的程序。

对于评测用例 $1$，$m = 10,~n = 100,~k \le 10^3$。

对于评测用例 $2$，$m = 10,~n = 100,~k \le 10^4$。

对于评测用例 $3$，$m = 30,~n = 100,~k \le 10^5$。

对于评测用例 $4$，$m = 180,~n = 100,~k \le 10^5$。

对于评测用例 $5$，$m = 10,~n = 100,~k \le 10^9$。

对于评测用例 $6$，$m = 30,~n = 100,~k \le 10^9$。

对于评测用例 $7$，$m = 180,~n = 100,~k \le 10^9$。

对于评测用例 $8$，$m = 600,~n = 100,~k \le 10^9$。

对于评测用例 $9$，$m = 800,~n = 100,~k \le 10^9$。

对于评测用例 $10$，$m = 1000,~n = 100,~k \le 10^9$。