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 \gt 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 \le n,m \le 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 \le ki \le 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.