#P2351. [BeiJing2011]Matrix

[BeiJing2011]Matrix

题目描述

给定一个 MM 行 NN 列的 0101 矩阵,以及 QQ 个 AA 行 BB 列的 0101 矩阵,你需要求出这 QQ 个矩阵哪些在原矩阵中出现过。 所谓 0101 矩阵,就是矩阵中所有元素不是 00 就是 11。

输入格式

输入文件的第一行为 M,N,A,BM,N,A,B,含义参见题目描述。 接下来 MM 行,每行 NN 个字符,非 00 即 11,描述原矩阵。 接下来一行为你要处理的询问数 QQ。 接下来 QQ 个矩阵,一共 Q×AQ\times A 行,每行 BB 个字符,描述 QQ 个 0101 矩阵。

输出格式

你需要输出 QQ 行,每行为 00 或者 11,表示这个矩阵是否出现过,00 表示没有出现过,11 表示出现过。

样例输入

3 3 2 2
111
000
111
3
11
00
11
11
00
11

样例输出

1
0
1

数据规模与约定

对于 100%100\% 的实际测试数据,M,N≤103M,N\le 10^3,Q=103Q=10^3。

对于 40%40\% 的数据,A=1A=1。

对于 80%80\% 的数据,A≤10A\le 10。

对于 100%100\% 的数据,A≤100A\le 100。