“高峰期走出去地铁巴士挤满了蚂蚁，
 计程车打开车门一只蝴蝶飞进去，
 猫头鹰指挥着红灯该何时才变绿”
               ——华晨宇《世界是个动物园》

每隔一段时间，世界上就会出现一种新的物种，现在，世界上总共有$n$种物种，为了方便描述，根据它们在世界上的出现顺序从早到晚将它们按照$1..n$的顺序编号。

自然界是十分友善的，在任意两种物种$x,y(1\le x< y\le n)$之间，都有一个“保护关系”，这种关系是单向的，要么是$x$想保护$y$，要么是$y$想保护$x$，注意，不会存在$x,y$使得$x$和$y$都想保护对方。

但是，自然界同时也是十分残忍的，或天灾，或人祸，或种间竞争，动物们总是避免不了种种的灾难。

为了更好的抵抗到来的灾难，有些动物决定结盟。

结盟的规则是这样的，对于三种动物$x,y,z(x\neq y,x\neq z,y\neq z)$，如果$x$想保护$y$，$y$想保护$z$，$z$想保护$x$，那么他们就会在同一个联盟里面。

比如说(1,2,3),(2,3,4)都是满足上面的条件的，那么最后1,2,3,4都会在同一个联盟里面。

然而，时至今日，由于物种的数量变得十分多，物种间的“保护关系”已经变得十分复杂了。

我们这样定义物种间的“保护关系”：

对于物种$i$，我们给出$i$与$1..i-1$的“保护关系”，具体的，给出$s_i$个区间$[l_{i,j},r_{i,j}] (1\le l_{i,j}\le r_{i,j}< i)$，这些区间两两之间交集为空，对于$x\in[1,i-1]$，如果存在$j(1\le j\le s_i)$满足$x\in[l_{i,j},r_{i,j}]$，那么$i$与$x$之间的关系就是$i$想保护$x$，否则就是$x$想保护$i$。

而对于物种$i$与物种$x(i+1\le x\le n)$之间的“保护关系”，会在$x$与$1..x-1$的“保护关系”中被定义。

这样显然不重不漏地定义了两两物种之间的“保护关系”。

动物中的生物学家们决定探究物种在演变过程中的变化，一个很重要的课题就是每个时期联盟的数量。

作为动物中的佼佼者，生物学家们希望你能帮助他们求出，对于$i\in[1,n]$，在物种$i$在这个世界上出现之后动物中的联盟的数量。

输入格式

第一行两个整数$n$和$ty$，表示物种的数量以及是否强制在线（$ty$为$1$表示强制在线，$ty$为$0$表示不强制在线）。

接下来$n$行，其中第$i$行第一个整数$s_i$，表示区间的数量，接下来同一行$s_i$对整数$L_{i,j},R_{i,j}$，如果$ty=0$，那么$l_{i,j}=L_{i,j},r_{i,j}=R_{i,j}$，否则$l_{i,j}=(L_{i,j}+lastans-1)\mod i+1,r_{i,j}=(R_{i,j}+lastans-1)\mod i+1$，其中$lastans$为物种$i-1$来到这个世界后联盟的数量，特殊地，当$i=1$时，$lastans=0$.

$l_{i,j},r_{i,j}$的意义请参考题目。

输出格式

输出一行$n$个整数，其中第$i$个整数，表示物种$i$来到这个世界后联盟的数量。

样例一

input

10 0
0 
1 1 1 
1 1 1 
1 1 1 
2 4 4 1 1 
2 1 1 4 4 
2 1 1 3 6 
2 6 6 1 4 
2 4 4 1 1 
2 2 2 7 8

output

1 2 3 4 5 6 7 4 5 1

样例二

input

10 1
0 
1 0 0 
1 2 2 
1 2 2 
2 0 0 2 2 
2 2 2 5 5 
2 2 2 4 0 
2 7 7 2 5 
2 0 0 6 6 
2 7 7 2 3

output

1 2 3 4 5 6 7 4 5 1

样例三

见样例数据下载。

限制与约定

记$S$为$s_i$的和。 本题采用捆绑测试，每个子任务的时空限制以及数据范围不尽相同，请选手们认真查看。

提示

输入输出的数据量较大，建议使用读入输出优化。

样例2即为样例1的加密版本.

下载

样例数据下载