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.
Input
The first line of the input contains two integers $*n*$ and $*m*$ ($1 ≤ *n*, *m* ≤ 100 000$) — 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 $200 000$.
Output
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.
样例
3 4
3 3 4 1
4 1 3 4 2
3 3 1 4
2
1
3
2
5 5
2 3 1
4 5 1 3 2
4 2 1 3 5
1 3
2 5 3
3
1
4
0
1
4 6
3 4 5 3
2 6 3
2 3 6
3 3 6 5
0
0
2
1
1
2
题面与样例版权归 Codeforces 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。