Даны $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$ — это множество всех последовательностей $c$, удовлетворяющих условиям $1\leq c_i\leq d_i$ и $\oplus_{i=1}^m a_{i,c_i}=t$.

Входные данные

В первой строке заданы три целых положительных числа $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$.