问题 F: 公共汽车

问题 F: 公共汽车

时间限制: 2 Sec  内存限制: 512 MB
提交: 21  解决: 5
[提交][状态][讨论版][命题人:]

题目描述

太喜欢怠速的感觉蝉羽般柔软

老子过函谷关的心态不过这样悠闲

飞奔

像驿道的信使

风速快感向世界宣布信念能够战胜自然

不会有阮籍的穷途之哭人生的止境绝不是终点颠簸坎坷只能证明外在的不平凡

心中的青牛一定是神仙谁的谁喜欢

哪怕是小绵羊爱惜得像宝贝一般

   


 人类的发展总离不开一代又一代的探险者先驱。追寻前人的轨迹,今天的darling到了一个有趣的城市,02居住的城市一样有趣。

    在这个城市中有n个站台和m条公交线路,i条公交线路由t[i]个站台组成,记为si_1,si_2...si_t[i].0时刻,i辆公交车会处在si_1站台,之后每个时刻公交都会到达路线中的下一个站台.

    当公交达终点站后,它下一个时刻将会回到出发的站台,注意一座站台可能在一条线路中出现多次,但不会相邻。

    在0时刻darling处在站台1。如果在某一时刻darling和公交在同一个站台,那么darling就可以上这辆公交车,并在任意时刻下车,上下车的过程并不会花费时间。作为一位环保的优秀旅行家,darling热爱乘坐公交出行。现在darling想要知道,如果他只乘坐公交出行,他分别能最早在何时到达每个站台,或是告诉他这是不可能的。

注意,darling一次只能乘坐一辆车,但在通往某个站台的过程中,darling可以乘坐许多辆不同的公交车。

输入

输入的第一行是两个整数n,m;分别表示站台和线路的个数。

   接下来的m行,每行的第一个数为t[i],表示线路的长度,随后的t[i]个整数描述一条公交线路。

输出

共输出1n-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

提示


对于10%的数据,n<=3,m=1,t[i]<=4



对于20%的数据,n,m<=10,Σt[i]<=300



对于35%的数据,n,m<=50,Σt[i]<=300



对于50%的数据,n,m<=1000,Σt[i]<=20000



对于65%的数据,n,m<=5000,Σt[i]<=100000



对于100%的数据,n,m<=100000,Σt[i]<=200000

[提交][状态]