Problem Description

Electro elemental totems have the following properties:

1. Each totem has $m$ states, one of $0,1,\cdots,m-1$.
2. When a totem is attacked once, it moves to the next state (the next state of $m-1$ is $0$).
3. When a certain totem is attacked once, it will also cause some other totems to move to the next state together.

When the states of all $n$ totems are the same, the puzzle is solved. However, player A thinks the totem puzzles in the game are too easy: he can solve them by using Keqing’s “Zhan Jin Niu Za” to attack all the totems randomly once, so he starts thinking about a more complex version.

Now there are $n$ Electro elemental totems, and each totem has $m$ states. For each totem $i$, when it is attacked, there are $k_i$ other totems that will move to the next state together with it.

Given the initial state $s$ and the target state $t$ of the $n$ Electro elemental totems, compute how many times you need to attack each totem in order to transform the totems from state $s$ to $t$.

If there is no solution, output niuza.

Input Format

The first line contains two positive integers $n,m\ (1\le n\le100,m\le10^9)$. It is guaranteed that $m$ is prime.

In the next $n$ lines, line $i$ contains the following data:

• First read an integer $k\ (0\le k<n)$, which indicates how many totems will be triggered when attacking this totem.
• Then read $k$ integers; the $j$-th integer is $a_j\ (1\le a_j \le n, a_j\neq i$ and $a_{j-1}<a_j)$, indicating the index of a totem triggered by totem $i$.

Then there are two more lines:

The first line contains $n$ integers; the $i$-th integer is $s_i$, representing the initial state of the $i$-th Electro elemental totem, where $s_i\ (0\le s_i <m)$.

The second line contains $n$ integers; the $i$-th integer is $t_i$, representing the target state of the $i$-th Electro elemental totem, where $t_i\ (0\le t_i <m)$.

Output Format

If there is a solution, output $n$ integers each less than $m$, representing how many times you should attack each totem. Separate them with spaces. If there are multiple solutions, output any one of them.

If there is no solution, output niuza.

3 3
1 3
2 1 3
1 2
0 0 0
0 2 1

2 1 1

3 3
2 2 3
2 1 3
1 1
0 0 0
0 1 2

niuza

Hint

Translated by ChatGPT 5