Description

Xiao Li is a famous furniture designer who has already designed $N$ unique pieces of furniture. To accurately evaluate the quality of the furniture, each piece is scored on $K$ different criteria, such as aesthetics, material quality, and practicality. Each criterion is represented by a non-negative integer. Furniture $a$ is said to be able to replace furniture $b$ if all $K$ scores of furniture $a$ are greater than or equal to the corresponding scores of furniture $b$.

Xiao Li plans to design a new batch of furniture, where the sum of the scores for each piece of furniture does not exceed $S$. The new furniture can be divided into $T$ categories. For the $N$ already designed pieces, each category of new furniture divides the $N$ pieces into two sets, $A$ and $B$, such that the new furniture can replace any piece in $B$, but cannot replace any piece in $A$. Xiao Li wants to know the design space for each category of new furniture, i.e., how many possible design schemes exist. Two design schemes are considered different if there is at least one criterion score that differs. Note that a new design scheme may be identical to one of the $N$ already designed pieces.

Input

The first line contains three positive integers $K, S, N$.

The next $N$ lines each contain $K$ non-negative integers, representing the scores of the $K$ criteria for each piece of furniture. Furniture is numbered starting from 1.

The next line contains a positive integer $T$, representing the number of categories of new furniture.

The following $T$ lines each contain a sequence of $N$ integers (either 0 or 1). If the $i$-th number is 0, it means this category of furniture does not replace the $i$-th piece of the already designed furniture; if the $i$-th number is 1, it means this category of furniture must replace the $i$-th piece of the already designed furniture.

Constraints

There are 20 test cases in total: 2 test cases: $S \le 50, K \le 5, N \le 5, T \le 10$. 2 test cases: $S \le 10\,000, K \le 2, N \le 20, T \le 100\,000$. 2 test cases: $S \le 5\,000, K \le 20, N \le 15, T \le 30\,000$. 6 test cases: $S \le 10\,000, K \le 30, N \le 20, T = 1$. * 8 test cases: $S \le 10\,000, K \le 30, N \le 20, T \le 100\,000$.

Output

The output should contain $T$ lines, each containing a non-negative integer representing the number of design schemes for that category.

Examples

Input 1

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

Output 1

13
2
5
1