Codeforces Round 443 (Div. 1) |
---|
Закончено |
Недавно в Берляндии начал проводится спортивный турнир по 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
В первом примере:
В первом турнире участвует один спортсмен, он и является победителем.
Во втором турнире два спортсмена, каждый из которых может обыграть другого, в зависимости от вида спорта.
В третьем турнире третий игрок побеждает любого в любом виде спорта, и он победит при любой схеме.
Название |
---|