← 返回题目列表

Codeforces · 878/C

C. 锦标赛

中文机器翻译题面 查看原题

最近,k种运动的锦标赛在伯兰拉开帷幕。瓦夏想通过赌注赚钱。

比赛的方案非常神秘,并未完全公开。比赛是连续举行的,每场比赛都有两名尚未离开比赛的运动员。每场比赛可以在 k 种运动中的任何一种中进行。失败者离开比赛。最后剩下的运动员成为获胜者。除此之外,该方案可以是任意的,不会提前公开。

Vasya 了解运动员在各种运动中的力量。他相信力量较高的运动员总是获胜。

锦标赛每年举行一次,每年都会有一名新参与者加入。在第一届比赛中,只有一名运动员参加,第二届比赛中有两名运动员参加,依此类推。 Vasya 在过去的 n 年里一直在观看比赛。帮助他找出 n 场比赛中每场比赛可能获胜者的数量。

输入

第一行包含两个整数 n 和 k (1 ≤ n ≤ 5·104, 1 ≤ k ≤ 10)——分别是锦标赛的数量和运动种类的数量。

接下来的 n 行每行包含 k 个整数 si1, si2, ..., sik (1 ≤ sij ≤ 109),其中 sij 是第 j 种运动中第 i 名运动员的力量。拥有较高力量的运动员总是获胜。可以保证的是,对于任何类型的运动来说,所有这些力量都是不同的。

输出

对于 n 场比赛中的每场比赛,输出能够获胜的竞争者的数量。

示例

输入 #1

3 2
1 5
5 1
10 10

输出 #1

1
2
1

输入 #2

3 2
2 2
3 3
1 10

输出 #2

1
1
3

输入 #3

3 2
2 3
1 1
3 2

输出 #3

1
1
2

注意

在第一个示例中:

在第一场比赛中只有一名运动员,他是获胜者。

在第二场比赛中,有两名运动员,每个人都可以击败另一个运动员,具体取决于运动类型。

在第三场比赛中,两项运动中最强的第三名运动员,因此无论方案如何,他都是获胜者。