1975: Cyclic Cipher
Description
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 ki.
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 10100 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 ki (1≤ki≤40)− the number of integers in the sequence, proceeded by ki 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 10100 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