給定 $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$ 的集合。

輸入格式

第一行輸入三個正整數 $n, m, k$。

接下來依序輸入 $F_1, \dots, F_m$。

對於每個 $F_i$：

輸入一行一個正整數 $d_i$。

接下來一行輸入 $d_i$ 個非負整數 $a_{i, j}$。

接下來一行輸入 $d_i$ 個正整數 $b_{i, j}$。

輸出格式

輸出一行 $2^n$ 個整數 $S_0, \dots, S_{2^n-1}$。

範例

範例輸入 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

資料範圍

$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$。