题目描述

在这个城市中有$n$个站台和$m$条公交线路，第$i$条公交线路由$t_i$个站台组成，记为 $s_i,1, s_i,2,…,s_i,t_i$。在$0$时刻，第$i$辆公交车会处在$s_i,1$站台，之后每个时刻公交都会到达路线中的下一个站台。当公交车到达终点站后，它下一个时刻将会回到出发的站台，注意一个站台可能在一条线路中出现多次，但不会相邻。 在$0$时刻，蒜头处在站台$1$。如果在某一时刻蒜头和公交在同一个站台，那么蒜头就可以上这辆公交车，并在任意时刻下车，上下车的过程并不会花费时间。现在蒜头想要知道，如果他只乘坐公交车出行，他分别能最早在何时到达每个站台，或是告诉他这是不可能的。 注意，蒜头一次只能乘坐一辆车，但在通往某个站台的过程中，蒜头可以乘坐许多辆不同的公交车。

输入

输入的第一行是两个整数$n,m$，分别表示站台和线路的个数。 接下来的$m$行，每行的第一个数为$t_i$，表示线路的长度，随后的$t_i$个整数描述一条公交线路。

输出

共输出$1$行$n-1$个数，第$i$个数表示到达站台$i+1$的最短时间。如果不能到达，输出$-1$。

输入样例

8 4
2 5 4
3 6 1 2
4 4 2 1 3
2 7 8

输出样例

2 3 4 6 3 -1 -1

提示

【数据规模】 100%的数据，$t_i≥2$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共8个测试点，非原站或官方原始数据。总分100分。