You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

有一个包含k种项目的比赛，每年举办一次，它的比赛机制很特殊。

首先，从比赛开始到结束，你都无法知道比赛的进行情况。比赛进行中，每轮将会任意选两名仍然在场的选手，任意选一种项目进行比试，输者立即被淘汰，如此重复，直到最后剩下的一名选手即为胜利者。

虽然不知道比赛的安排，但你事先知道每个选手每种项目的能力值。我们认为能力高的选手必定能赢。（数据保证同个项目中选手能 力值彼此不同）

这个比赛举办了n年，每年都会有一名新的选手加入。第一年仅有1 名选手，第二年有2名选手，以此类推。我们称第i年参赛的选手为第i名选手。现在需要你给出，对于每年的比赛，最终可能成为胜利者的选手有多少人？

Input

一行两个正整数n,k(1≤n≤5*100000,1≤k≤10)，表示比赛n年举办了n次，以及一共有k种项目

接下来n行，每行k个正整数si1,si2,si3…sik(1≤sij≤10)，表示第i名参赛选手的k项能力值。注意同个项目内能力高的选手必定能赢。数据保证同个项目中的能力值均互不相同。

Output

n行，每行一个数表示答案，即该年的比赛中，可能成为胜利者的人数。

Samples

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

输入 #4 见数据包

输出 #4 见数据包

样例解释

样例 #1 第1年，选手1可能成为胜利者，因为只有一个人

第2年，选手1,2都可能成为胜利者，因为选手1可以在第2个项目赢选手2，而选手2可以在第1个项目赢选手1

第3年，选手3可能成为胜利者，因为选手3各项能力值均为最高

Limitation