给你 $k$ 个不同的多项式 $a_1(x), \dots, a_k(x)$ 和 $m$ 个不同的多项式 $b_1(x), \dots, b_m(x)$。

每个多项式 $a_i(x)$（$1 \le i \le k$）的次数不超过 $n$，每个多项式 $b_j(x)$（$1 \le j \le m$）的次数不超过 $2n$。

对于每个多项式 $b_j(x)$（$1 \le j \le m$），你需要求出满足 $a_u(x) \cdot a_v(x) = b_j(x)$ 的二元组 $(u, v)$（$u \le v$）的数量。

输入格式

第一行包含三个整数 $k$，$m$ 和 $n$（$1 \le k \le 40\,000$，$1 \le m \le 150$，$0 \le n \le 20$）。

接下来的 $k$ 行，每行包含 $n + 1$ 个整数，表示多项式 $a_i(x) = a_{i,0} + a_{i,1}x + \dots + a_{i,n-1}x^{n-1} + a_{i,n}x^n$（$1 \le i \le k$）的系数 $a_{i,0}, a_{i,1}, \dots, a_{i,n}$。

接下来的 $m$ 行，每行包含 $2n + 1$ 个整数，表示多项式 $b_j(x) = b_{j,0} + b_{j,1}x + \dots + b_{j,2n-1}x^{2n-1} + b_{j,2n}x^{2n}$（$1 \le j \le m$）的系数 $b_{j,0}, b_{j,1}, \dots, b_{j,2n}$。

所有系数的绝对值均不超过 $10^6$。

输出格式

输出恰好 $m$ 行，其中第 $j$ 行应包含满足 $a_u(x) \cdot a_v(x) = b_j(x)$ 的整数对 $(u, v)$（$1 \le u \le v \le k$）的数量。

样例

输入样例 1

2 2 0
-2
2
-4
4

输出样例 1

1
2

输入样例 2

6 3 2
0 -1 1
0 1 1
-1 0 1
0 1 0
-1 1 0
1 1 0
0 -1 0 1 0
0 0 -1 0 1
0 0 1 0 -1

输出样例 2

3
1
0