Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

C. Турнир
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Недавно в Берляндии начал проводится спортивный турнир по k видам спорта. А Вася хочет подзаработать на ставках.

Схема турнира весьма загадочна и полностью не раскрывается. Состязания проходят последовательно, в каждом их них участвуют два спортсмена, которые ещё не вылетели из турнира. Каждое состязание может проходить в любом из k видов спорта. Проигравший спортсмен вылетает из турнира. Последний оставшийся спортсмен становится победителем турнира. В остальном схема может быть произвольной, заранее она не разглашается.

Васе известны способности спортсменов к разным видам спорта. Он считает, что более способный спортсмен всегда победит менее способного.

Турнир проводится каждый год, и каждый раз к нему присоединяется один новый спортсмен. В первом турнире участвовал лишь один спортсмен, во втором – два, и так далее. Вася следит за турниром в течение n лет. Помогите ему для каждого из n турниров узнать, сколько существует претендентов на победу в турнире.

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

В первой строке содержатся числа n и k (1 ≤ n ≤ 5·104, 1 ≤ k ≤ 10) — количество турниров и видов спорта, соответственно.

Следующие n строк содержат по k целых чисел si1, si2, ..., sik (1 ≤ sij ≤ 109), где sij — способность спортсмена i к виду спорта j. Спортсмен с большей способностью всегда выигрывает. Гарантируется, что для каждого вида спорта способности всех спортсменов различны.

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

Для каждого из n турниров выведите количество возможных победителей.

Примеры
Входные данные
3 2
1 5
5 1
10 10
Выходные данные
1
2
1
Входные данные
3 2
2 2
3 3
1 10
Выходные данные
1
1
3
Входные данные
3 2
2 3
1 1
3 2
Выходные данные
1
1
2
Примечание

В первом примере:

В первом турнире участвует один спортсмен, он и является победителем.

Во втором турнире два спортсмена, каждый из которых может обыграть другого, в зависимости от вида спорта.

В третьем турнире третий игрок побеждает любого в любом виде спорта, и он победит при любой схеме.