$n, m, k$와 $m$개의 수열 쌍 $(a_i, b_i)$가 주어집니다. $|a_i| = |b_i| = d_i$라고 할 때, 모든 $0 \leq t < 2^n$에 대하여 다음 식을 $10^{18} + 125953$으로 나눈 나머지를 구하십시오.

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

예제

입력 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