题目内容

我们假设亚运会的lol比赛遵循如下规则：

全是淘汰赛，每场比赛会从还没被淘汰的队伍里选两队进行比赛，输的一方被淘汰
比赛按顺序依次进行，上一场比赛结束后下一场比赛才开始
假设比赛日程完全随机，即这场比赛的双方会从上场比赛结束后还没被淘汰的所有队伍中随机挑选两队
最后剩下没被淘汰过的那只队伍获得冠军

作为一个竞技比赛，队伍之间的输赢也是不确定的。而小C认真研究了所有参与比赛的n个队伍之后，他给每支队伍都评估了k个属性值，比如可能是发育，团战，配合等。

我们假设小C已经非常的专业，两支队伍比赛，只要一方队伍有一种属性值比另一方高，那么这支队伍就有可能赢。

现在小C想要知道对于每个 i，如果只有前 i 个队伍比赛，那么可能获的冠军的队伍有多少个？ 输入格式

第一行两个正整数 n, k。

接下来 n 行，每行 k 个正整数，第 i+1 行表示第 i 个球队的每项属性值是多少。 输出格式

输出 n 个数，第 i 个数表示前 i 个球队比赛的话，可能获胜的球队的数目。 样例 1 输入

3 2 1 2 2 1 3 3

样例 1 输出

1 2 1

子任务 子任务名 评分方式 时间限制 内存限制 说明 分数 默认子任务 求和 1000 ms 512 MB

共 10 个测试点 100 提示

样例 1 解释：

只有第一个球队，可能获胜的球队有 1 个。

前两个球队互相都可能获胜，可能获胜的球队有 2 个。

全部球队比赛最后一定是第三个球队获胜，可能获胜的球队有 1 个。

数据范围：

对于 30 % 的数据，n ≤ 2000。

另有 10 % 的数据，k = 1。

对于 100 % 的数据，n ≤ 100000，1 ≤ k ≤ 5 ，保证 n 个球队的每个属性值都是 1 ~ n 的排列。