“At peak hours, the subways and buses are packed with ants, A butterfly flies into a taxi as the door opens, An owl directs the red light on when to turn green.” ——Hua Chenyu, The World is a Zoo

From time to time, a new species appears in the world. Currently, there are $n$ species in total. For convenience, they are numbered $1$ to $n$ based on the order of their appearance, from earliest to latest.

Nature is very kind. Between any two species $x$ and $y$ ($1 \le x < y \le n$), there exists a "protection relationship." This relationship is unidirectional: either $x$ wants to protect $y$, or $y$ wants to protect $x$. Note that it is impossible for both $x$ and $y$ to want to protect each other.

However, nature is also very cruel. Whether due to natural disasters, human-made catastrophes, or interspecies competition, animals cannot avoid various disasters.

To better resist incoming disasters, some animals decide to form alliances.

The rules for forming an alliance are as follows: for three animals $x, y, z$ ($x \neq y, x \neq z, y \neq z$), if $x$ wants to protect $y$, $y$ wants to protect $z$, and $z$ wants to protect $x$, then they will be in the same alliance.

For example, if $(1, 2, 3)$ and $(2, 3, 4)$ both satisfy the above condition, then $1, 2, 3, 4$ will all be in the same alliance.

However, as of today, because the number of species has become very large, the "protection relationships" between species have become very complex.

We define the "protection relationship" between species as follows:

For species $i$, we are given the "protection relationships" between $i$ and $1 \dots i-1$. Specifically, we are given $s_i$ intervals $[l_{i,j}, r_{i,j}]$ ($1 \le l_{i,j} \le r_{i,j} < i$), where these intervals are pairwise disjoint. For $x \in [1, i-1]$, if there exists a $j$ ($1 \le j \le s_i$) such that $x \in [l_{i,j}, r_{i,j}]$, then the relationship between $i$ and $x$ is that $i$ wants to protect $x$; otherwise, $x$ wants to protect $i$.

The "protection relationship" between species $i$ and species $x$ ($i+1 \le x \le n$) is defined when considering the relationships for species $x$ with $1 \dots x-1$.

This clearly defines the "protection relationship" between every pair of species without overlap or omission.

Biologists among the animals have decided to investigate the changes in species during the evolutionary process. An important topic is the number of alliances at each stage.

As leaders among the animals, the biologists hope you can help them calculate, for each $i \in [1, n]$, the number of alliances among the animals after species $i$ appears in the world.

Input

The first line contains two integers $n$ and $ty$, representing the number of species and whether the input is forced online ($ty = 1$ means forced online, $ty = 0$ means not forced online).

The next $n$ lines each describe the relationships for species $i$. The first integer is $s_i$, the number of intervals. This is followed by $s_i$ pairs of integers $L_{i,j}, R_{i,j}$. If $ty = 0$, then $l_{i,j} = L_{i,j}$ and $r_{i,j} = R_{i,j}$. Otherwise, $l_{i,j} = (L_{i,j} + lastans - 1) \pmod i + 1$ and $r_{i,j} = (R_{i,j} + lastans - 1) \pmod i + 1$, where $lastans$ is the number of alliances after species $i-1$ arrived in the world. Specifically, when $i=1$, $lastans = 0$.

Please refer to the problem description for the meaning of $l_{i,j}$ and $r_{i,j}$.

Output

Output a single line containing $n$ integers, where the $i$-th integer represents the number of alliances after species $i$ arrives in the world.

Examples

Input 1

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

1 2 3 4 5 6 7 4 5 1

Input 2

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 2

1 2 3 4 5 6 7 4 5 1

Input 3

(See sample data download)

Constraints

Let $S$ be the sum of $s_i$. This problem uses bundled testing. Each subtask has different time and memory limits and data ranges; please check them carefully.

Note

The input and output data volume is large; it is recommended to use fast I/O.

Example 2 is the encrypted version of Example 1.