Submatrix Occurrence Check

You are given a binary matrix \( M \) of size \( m \times n \) (i.e. each element is either \(0\) or \(1\)) and \( q \) query matrices, each of size \( a \times b \). Your task is to determine for each query matrix if it appears as a contiguous submatrix in the original matrix.

A binary matrix (also known as a \(01\) matrix) means that every element is either \(0\) or \(1\).

More formally, given a matrix \( X \) and a query matrix \( Y \) of dimensions \(a \times b\), you must check if there exists an index \( (i,j) \) such that for all \( 0 \leq x < a \) and \( 0 \leq y < b \), \[ X_{i+x,j+y} = Y_{x,y} \] If such an \( (i,j) \) exists, output 1; otherwise, output 0.

inputFormat

The input contains several parts:

1. The first line contains two integers \( m \) and \( n \), representing the number of rows and columns of the main matrix.
2. The next \( m \) lines each contain \( n \) integers (either 0 or 1) separated by spaces, representing the main matrix.
3. The next line contains a single integer \( q \), representing the number of query matrices.
4. For each query matrix, the first line contains two integers \( a \) and \( b \), the dimensions of the query matrix, followed by \( a \) lines each containing \( b \) integers (0 or 1) separated by spaces.

outputFormat

For each query matrix, print a line containing a single integer: "1" if the query matrix appears as a contiguous submatrix in the main matrix, and "0" otherwise.

sample

3 4
0 1 0 1
1 1 0 0
0 1 0 1
2
2 2
1 0
1 0
2 2
0 1
0 0

1
0