Cho $n,m,k$ và $m$ cặp dãy $(a_i,b_i)$, đặt $|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$, $\oplus_{i=1}^m a_{i,c_i}=t$.

Dữ liệu vào

Dòng đầu tiên nhập vào ba số nguyên dương $n,m,k$.

Tiếp theo lần lượt nhập $F_1,\dots,F_m$.

Với mỗi $F_i$:

Dòng đầu tiên nhập vào một số nguyên dương $d_i$.

Dòng tiếp theo nhập vào $d_i$ số nguyên không âm $a_{i,j}$.

Dòng tiếp theo nhập vào $d_i$ số nguyên dương $b_{i,j}$.

Dữ liệu ra

In ra trên một dòng $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$ (với $P = 10^{18}+125953$).