← 返回题目列表

Codeforces · 722/F

F. 循环密码

中文机器翻译题面 查看原题

给你 n 个序列。每个序列由正整数组成,不超过m。一个序列中的所有整数都是不同的,但同一个整数可能出现在多个序列中。第 i 个序列的长度为 ki。

每个序列中的第二个整数向左移动一位,即位置 i > 1 处的整数移至位置 i - 1,而第一个整数变为最后一个。

每秒我们获取每个序列的第一个整数并将其写入一个新数组。然后,对于从 1 到 m 的每个值 x,我们计算仅由元素 x 组成的数组的最长段。

以上操作执行10100秒。对于从 1 到 m 的每个整数,找出此时找到的最长线段。

输入

输入的第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 100 000) - 序列的数量以及序列中可以出现的最大整数。

然后按照 n 行提供序列。它们每个都以整数 ki (1 ≤ ki ≤ 40) 开头——序列中的整数个数,后面是 ki 个正整数——序列的元素。保证每个序列中的所有整数都是两两不同且不​​超过 m。

所有序列的总长度不超过200 000。

输出

打印 m 个整数,其中第 i 个整数应等于数组的最长段的长度,并且在前 10100 秒内所有值都等于 i。

示例

输入 #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