Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

chinese remainder theorem

data structures

implementation

number theory

two pointers

*2800

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Cyclic Cipher

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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.

Examples

Input

3 4

3 3 4 1

4 1 3 4 2

3 3 1 4

Output

2

1

3

2

Input

5 5

2 3 1

4 5 1 3 2

4 2 1 3 5

1 3

2 5 3

Output

3

1

4

0

1

Input

4 6

3 4 5 3

2 6 3

2 3 6

3 3 6 5

Output

0

0

2

1

1

2

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/14/2024 15:44:48 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|