P8038 [COCI 2016/2017 #7] BAZA

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.

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.

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

**[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](https://hsin.hr/coci/archive/2016_2017/) [CONTEST 7](https://hsin.hr/coci/archive/2016_2017/contest7_tasks.pdf) T1 BAZA_**. Using the original testdata configuration, the full score is $50$ points. Translated and organized by [Eason_AC](https://www.luogu.com.cn/user/112917). Translated by ChatGPT 5