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

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

输出样例 #1

2
1
3
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

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

输出样例 #3

0
0
2
1
1
2