题面描述

给定 $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$，$\oplus_{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}$。

样例数据

样例输入

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

样例输出

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