Matching Rows in a Database

Mirko has secured a summer internship at a large IT company. This company has built a huge database containing \(N\) rows and \(M\) columns. The integer in the \(i\)-th row and \(j\)-th column is \(A_{i,j}\).

On his first day, he receives \(Q\) queries. Each query consists of \(M\) integers \(B_1, B_2, \dots, B_M\). Unfortunately, some numbers are lost during transmission, and the system replaces them with \(-1\).

For each query, Mirko needs to answer how many rows in the database match the numbers in the query. More formally, for each query he must count the number of integers \(i\) (with \(1 \leq i \leq N\)) such that for every \(j\) in \([1, M]\), either \(B_j = -1\) or \(B_j = A_{i,j}\). For example, if \(M=3\) and a query is given as -1 3 2, then the row matches if its first column can be any integer, its second column is exactly \(3\), and its third column is exactly \(2\).

inputFormat

The first line contains two integers \(N\) and \(M\) \((1 \le N, M \le 10^5)\) representing the number of rows and columns in the database.

Each of the next \(N\) lines contains \(M\) integers, representing a row of the database.

The next line contains the integer \(Q\) \((1 \le Q \le 10^5)\), the number of queries.

Each of the next \(Q\) lines contains \(M\) integers \(B_1, B_2, \dots, B_M\), where each \(B_j\) is either an integer or \(-1\) (indicating a wildcard that matches any number).

outputFormat

For each query, output a single integer on a new line indicating the number of rows that match the given query.

sample

3 3
1 2 3
4 5 6
7 8 9
2
-1 2 -1
1 -1 3

1
1