Cyclic Cipher

题面翻译

给定 $n$ 个数列，第 $i$ 个数列包含 $k_i$ 个不超过 $m$ 的互不相同的正整数(从 $1$ 开始标号)。

每一秒将每个数列中的数左移一个位置(即将每个数的下标 $-1$ , 下标 $1$ 的数下标变为 $k_i$), 并记录由每个数列的第一个数组成的序列。

$10^{100}$ 秒过后，对于所有的 $1\leqslant x\leqslant m$ ，求 $x$ 在记录下来的序列中出现的最长的连续的一段长度。

题目描述

You are given $n$ sequences. Each sequence consists of positive integers, not exceeding $m$ . All integers in one sequence are distinct, but the same integer may appear in multiple sequences. The length of the $i$ -th sequence is $k_{i}$ .

Each second integers in each of the sequences are shifted by one to the left, i.e. integers at positions i>1 go to positions $i-1$ , while the first integers becomes the last.

Each second we take the first integer of each sequence and write it down to a new array. Then, for each value $x$ from $1$ to $m$ we compute the longest segment of the array consisting of element $x$ only.

The above operation is performed for $10^{100}$ seconds. For each integer from $1$ to $m$ find out the longest segment found at this time.

输入格式

The first line of the input contains two integers $n$ and $m$ ( $1<=n,m<=100000$ ) — the number of sequences and the maximum integer that can appear in the sequences.

Then follow $n$ lines providing the sequences. Each of them starts with an integer $k_{i}$ ( $1<=k_{i}<=40$ ) — the number of integers in the sequence, proceeded by $k_{i}$ positive integers — elements of the sequence. It's guaranteed that all integers in each sequence are pairwise distinct and do not exceed $m$ .

The total length of all sequences doesn't exceed $200000$ .

输出格式

Print $m$ integers, the $i$ -th of them should be equal to the length of the longest segment of the array with all its values equal to $i$ during the first $10^{100}$ seconds.

样例 #1

样例输入 #1

3 4
3 3 4 1
4 1 3 4 2
3 3 1 4

样例输出 #1

2
1
3
2

样例 #2

样例输入 #2

5 5
2 3 1
4 5 1 3 2
4 2 1 3 5
1 3
2 5 3

样例输出 #2

3
1
4
0
1

样例 #3

样例输入 #3

4 6
3 4 5 3
2 6 3
2 3 6
3 3 6 5

样例输出 #3

0
0
2
1
1
2