题目描述

雷元素方碑具有如下性质：

1. 具有 �m 种状态，0,1,⋯ ,�−10,1,⋯,m−1 中的一种；
2. 方碑受到一次攻击会进入下一个状态（�−1m−1 的下一个状态是00）；
3. 某个方碑受到一次攻击时会带动其它一些方碑一起进入下一个状态。

当 �n 个方碑的状态相同时，解谜成功。但是小 A 觉得游戏里的方碑解谜太简单了，只需要使用刻晴的“斩尽牛杂”将元素方碑全部胡乱攻击一遍就能解谜成功，于是他开始思考更复杂的版本。

现在有 �n 个雷元素方碑，每个雷元素方碑有 �m 种状态。对于每个方碑 �i ，当它受到攻击时，都有 ��ki​ 个其它方碑和它一起进入下一个状态。

给定 �n 个雷元素方碑的初始状态 �s 和终止状态 �t，请你计算需要分别攻击每个方碑多少下，才能将雷元素方碑从状态 �s 变换到 �t。

如果无解请输出niuza。

输入格式

第一行读入两个正整数 �,�(1≤�≤100,�≤109)n,m (1≤n≤100**,m≤109)，​保证 �m 为素数**​。

接下来 �n 行，第 �i 行会读取如下数据：

• 先读入一个数字 �(0≤�<�)k (0≤k<n)，表示攻击该方碑会带动的方碑数。
• 接下来读入 �k 个数字，第 �j 个数 ��(1≤��≤�,��≠�aj​ (1≤aj​**≤n,aj​**=i 且 ��−1<��)aj**−1​**<aj​) 表示 �i 方碑带动的方碑编号。

接下来两行：

第一行读入 �n 个数，第 �i 个数 ��si​ 表示第 �i 个雷元素方碑的初始状态 ��(0≤��<�)si​ (0≤si​**<m)**。

第二行读入 �n 个数，第 �i 个数 ��ti​ 表示第 �i 个雷元素方碑的终止状态 ��(0≤��<�)ti​ (0≤ti​**<m)**​。

输出格式

如果有解，输出 �n 个小于 �m 的数，分别表示应该攻击每个方碑多少次，用空格隔开。对于多个解，输出任意一个即可。

如果无解，请输出 niuza。

输入输出样例

输入 #1复制

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

输出 #1复制

2 1 1

输入 #2复制

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

输出 #2复制

ni