Cho $n, m, k$ và $m$ cặp dãy $(a_i, b_i)$, với $|a_i| = |b_i| = d_i$. Với mọi $0 \leq t < 2^n$, hãy tính:

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

Trong đó $C_t$ là tập hợp tất cả các dãy $c$ thỏa mãn $1 \leq c_i \leq d_i$ và $\bigoplus_{i=1}^m a_{i,c_i} = t$.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên dương $n, m, k$.

Tiếp theo là dữ liệu cho $F_1, \dots, F_m$.

Với mỗi $F_i$:

Dòng đầu tiên chứa một số nguyên dương $d_i$.

Dòng tiếp theo chứa $d_i$ số nguyên không âm $a_{i,j}$.

Dòng tiếp theo chứa $d_i$ số nguyên dương $b_{i,j}$.

Dữ liệu ra

In ra một dòng gồm $2^n$ số nguyên $S_0, \dots, S_{2^n-1}$.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

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

Giới hạn

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