F. Циклический шифр
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задан набор из n последовательностей. Каждая из последовательностей состоит из целых положительных чисел, не превосходящих m. Все числа внутри одной последовательности различны, но одно и то же число может встречаться в разных последовательностях. Длина i-й последовательности равна ki.

Раз в секунду числа в каждой последовательности циклически сдвигаются на одну позицию влево, то есть числа на позициях i > 1 переходят на позиции i - 1, а первое число становится последним.

Каждую секунду будем выписывать первое число каждой последовательности в новый массив. Для всех чисел 1 до m найдем самый длинный подотрезок этого массива, все элементы которого равны этому числу.

Будем проделывать эту операцию на протяжении 10100 секунд. Для каждого числа от 1 до m определите самый длинный из подотрезков, найденных за это время.

Входные данные

В первой строке входных данных записаны два числа n и m (1 ≤ n, m ≤ 100 000) — количество последовательностей и максимальное число, которое может встретиться в последовательностях.

В следующих n строках даны сами последовательности. В каждой строке сначала записано число ki (1 ≤ ki ≤ 40) — количество чисел в последовательности, а затем ещё ki целых положительных чисел — сама последовательность. Гарантируется, что числа в каждой последовательности попарно различны и не превосходят m.

Суммарная длина всех последовательностей не превосходит 200 000.

Выходные данные

Выведите m чисел, i-е из которых равняется длине самого большого подотрезка, все числа в котором равны i и который встретился в выписываемом массиве за первые 10100 секунд.

Примеры
Входные данные
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