Problem Description

Given an $M$-row $N$-column $01$ matrix, and $Q$ $01$ matrices of size $A$ rows and $B$ columns, you need to determine which of these $Q$ matrices appear in the original matrix.

A $01$ matrix means that every element in the matrix is either $0$ or $1$.

Input Format

The first line of the input file contains $M, N, A, B$, as described above.

The next $M$ lines each contain $N$ characters, each being either $0$ or $1$, describing the original matrix.

The next line contains the number of queries $Q$.

Then follow $Q$ matrices, totaling $Q \times A$ lines, where each line contains $B$ characters, describing the $Q$ $01$ matrices.

Output Format

Output $Q$ lines. Each line should be $0$ or $1$, indicating whether the corresponding matrix appears in the original matrix: $0$ means it does not appear, and $1$ means it does.

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

1
0
1

Hint

For $100\%$ of the actual testdata, $1 \leq M, N \leq 1000$, and $Q = 1000$.

For $40\%$ of the testdata, $A = 1$.

For $80\%$ of the testdata, $A \leq 10$.

For $100\%$ of the testdata, $A \leq 100$.

Translated by ChatGPT 5