Problem Description

Mirko got a summer internship at a large IT company. The company built a large database with $N$ rows and $M$ columns, where the integer in row $i$ and column $j$ is $A_{i,j}$.

On his first day of work, he received $Q$ queries, and each query contains $M$ integers $B_1,B_2,\dots,B_M$. Unfortunately, some numbers were lost during transmission, and the database replaced them with $-1$. Mirko needs to answer how many rows in the database match all the numbers in the query. Formally, Mirko needs to find how many integers $i$ in the range $[1,N]$ satisfy that for all $j\in[1,M]$, either $B_j=-1$ or $B_j=A_{i,j}$. For example, if $M=3$ and a query is $-1~3~2$, then Mirko needs to find the number of rows where the first column can be any integer, the second column is $3$, and the third column is $2$.

Since Mirko is new to the internship, he hopes to get your help. Please help him answer these queries.

Input Format

The first line contains two integers $N, M$, representing the number of rows and columns of the database.
The next $N$ lines each contain $M$ integers, describing the database.
The next line contains an integer $Q$, representing the number of queries.
The next $Q$ lines each contain $M$ integers, describing one query.

Output Format

For each query, output one integer per line, representing the number of rows that satisfy the requirements.

4 3
1 5 2
2 3 4
4 3 2
5 4 6
3
-1 -1 2
-1 3 2
-1 -1 -1

2
1
4

3 8
6 5 97 99 82 50 95 1
85 62 11 64 94 84 88 19
43 99 11 64 94 84 31 19
3
-1 -1 11 64 94 84 -1 19
-1 -1 -1 99 -1 -1 -1 1
95 -1 -1 -1 -1 80 -1 -1

2
1
0

Hint

[Sample 1 Explanation]

For the first query, the first row and the third row satisfy the requirement that the third column is $2$.
For the second query, only the third row satisfies the requirement that the second column is $3$ and the third column is $2$.
For the third query, since no column value is required, all rows satisfy the requirements.

[Constraints]

For all testdata, $1\leqslant N,M\leqslant 10^3$, $1\leqslant Q\leqslant 50$, $1\leqslant A_{i,j}\leqslant 10^6$, and $B_j=-1$ or $1\leqslant B_j\leqslant 10^6$.

[Source]

This problem is from COCI 2016-2017 CONTEST 7 T1 BAZA. Using the original testdata configuration, the full score is $50$ points.

Translated and organized by Eason_AC.

Translated by ChatGPT 5