$n, m, k$ および $m$ 個の数列のペア $(a_i, b_i)$ が与えられます。ここで $|a_i| = |b_i| = d_i$ とします。すべての $0 \leq t < 2^n$ に対して、次を計算してください。

$$ S_t = \sum_{c \in C_t} \prod_{i=1}^m b_{i, c_i} \pmod{10^{18} + 125953} $$

ここで $C_t$ は、$1 \leq c_i \leq d_i$ かつ $\bigoplus_{i=1}^m a_{i, c_i} = t$ を満たす数列 $c$ の集合です。

入力

1行目に3つの正整数 $n, m, k$ が与えられます。

続いて $F_1, \dots, F_m$ が順に与えられます。各 $F_i$ について以下の形式で入力されます。

1行目に正整数 $d_i$。 次の行に $d_i$ 個の非負整数 $a_{i, j}$。 次の行に $d_i$ 個の正整数 $b_{i, j}$。

出力

1行に $2^n$ 個の整数 $S_0, \dots, S_{2^n-1}$ を出力してください。

制約

• $1 \leq n \leq 20$
• $1 \leq d_i \leq k \leq 10$
• $\sum_i 2^{d_i} \leq 2^{17}$
• $0 \leq a_{i, j} < 2^n$
• $1 \leq b_{i, j} < P$

入出力例

入力 1

4 3 4
3
5 1 4
1 1 4
4
8 2 7 3
11 13 9 6
4
10 0 2 2
7 9 8 3

出力 1

165 539 135 518 737 407 911 410 105 442 0 121 865 358 484 121