题目描述

给定一个 M 行 N 列的 01 矩阵（只包含数字 0 或 1 的矩阵），再执行 Q 次询问，每次询问给出一个 A 行 B 列的 01 矩阵，求该矩阵是否在原矩阵中出现过。

输入格式

第一行四个整数 M,N,A,B。

接下来一个 M 行 N 列的 01 矩阵，数字之间没有空格。

接下来一个整数 Q。

接下来 Q 个 A 行 B 列的 01 矩阵，数字之间没有空格。

输出格式

对于每个询问，输出 1 表示出现过，0 表示没有出现过。

样例

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

1
0
1

数据范围

$A≤100，M,N,B≤1000，Q≤1000$

来源

• NOI 2011 北京市选
• BZOJ2351
• 算法竞赛进阶指南