最近,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
注意
在第一个示例中:
在第一场比赛中只有一名运动员,他是获胜者。
在第二场比赛中,有两名运动员,每个人都可以击败另一个运动员,具体取决于运动类型。
在第三场比赛中,两项运动中最强的第三名运动员,因此无论方案如何,他都是获胜者。