小李是一位著名的家具设计师，他已设计出了 $N$ 件各具特色的家具。为了准确评价家具的质量，需要对家具的各项指标进行评分，如美观度、材质感、实用程度等，总共有 $K$ 项评分指标，每项指标都可以用一个非负整数来表示。如果家具 $a$ 的 $K$ 项指标得分均不小于家具 $b$ 的指标得分，则称家具 $a$ 可替代家具 $b$。

小李计划设计一批新家具，其中，每件家具各项指标得分的和不超过 $S$。新家具可以分为 $T$ 类。相对于已设计出的 $N$ 件家具，每类新家具都可将已设计出的 $N$ 件家具分成两部分 $A$ 和 $B$，该类新家具能替代 $B$ 中的家具，但不可替代 $A$ 中的家具。小李想知道每类新家具的设计空间有多大，即有多少种可选设计方案。在任何 $2$ 种设计方案中，只要有一个指标的得分值不同，就可视为不同的设计方案。另外，新设计方案中的家具可以与已设计出的 $N$ 件家具中的家具相同。

编程任务

给定一个整数 $S$ 和 $K$ 维空间中的 $N$ 个整点。$T$ 个询问，每个询问将 $N$ 个整点分为 $A$、$B$ 两类，求在 $K$ 维空间中有多少个整点 $x$ 满足：

(1) $x$ 的每一维是非负整数。 (2) $x$ 所有维度的和不超过 $S$。 (3) 对于每个 $A$ 类点 $A[i]$，都存在某一个维度 $j$，使得 $x[j] < A[i][j]$。 (4) 对于每个 $B$ 类点 $B[i]$，都有 $x[j] \geq B[i][j], 1 \leq j \leq K$。

输入格式

第一行 $3$ 个正整数 $K, S, N$。

接下来的 $N$ 行中，每行有 $K$ 个非负整数，表示每件家具的 $K$ 项指标得分。家具从 $1$ 开始编号。

再接着的一行中，有一个正整数 $T$，表示新家具可以分为 $T$ 类。

然后，接下来的 $T$ 行中，每行给出由 $N$ 个 $0$ 或 $1$ 组成的序列。第 $i$ 个数为 $0$，则表示该类家具不替代已经设计出的 $N$ 件家具中的第 $i$ 件家具；第 $i$ 个数为 $1$，则表示该类家具须替代第 $i$ 件家具。

输出格式

文件共有 $T$ 行，每行输出一个非负整数，表示设计方案数。

数据范围

共有 $20$ 个测试点：

• 有 $2$ 个测试点，$S \leq 50, K \leq 5, N \leq 5, T \leq 10$。
• 有 $2$ 个测试点，$S \leq 10\,000, K \leq 2, N \leq 20, T \leq 100\,000$。
• 有 $2$ 个测试点，$S \leq 5\,000, K \leq 20, N \leq 15, T \leq 30\,000$。
• 有 $6$ 个测试点，$S \leq 10\,000, K \leq 30, N \leq 20, T = 1$。
• 有 $8$ 个测试点，$S \leq 10\,000, K \leq 30, N \leq 20, T \leq 100\,000$。

样例

输入格式 1

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

输出格式 1

13
2
5
1