Recently a tournament in _k_ kinds of sports has begun in Berland. Vasya wants to make money on the bets.
The scheme of the tournament is very mysterious and not fully disclosed. Competitions are held back to back, each of them involves two sportsmen who have not left the tournament yet. Each match can be held in any of the _k_ kinds of sport. Loser leaves the tournament. The last remaining sportsman becomes the winner. Apart of this, the scheme can be arbitrary, it is not disclosed in advance.
Vasya knows powers of sportsmen in each kind of sport. He believes that the sportsmen with higher power always wins.
The tournament is held every year, and each year one new participant joins it. In the first tournament, only one sportsman has participated, in the second there were two sportsmen, and so on. Vasya has been watching the tournament for the last _n_ years. Help him to find the number of possible winners for each of the _n_ tournaments.
## Input
The first line contains two integers _n_ and _k_ (1 ≤ _n_ ≤ 5·104, 1 ≤ _k_ ≤ 10) — the number of tournaments and the number of kinds of sport, respectively.
Each of the next _n_ lines contains _k_ integers _s__i_1, _s__i_2, ..., _s__ik_ (1 ≤ _s__ij_ ≤ 109), where _s__ij_ is the power of the _i_\-th sportsman in the _j_\-th kind of sport. The sportsman with higher powers always wins. It's guaranteed that for any kind of sport all of these powers are distinct.
## Output
For each of the _n_ tournaments output the number of contenders who can win.
[samples]
## Note
In the first sample:
In the first tournament there is only one sportsman, and he is the winner.
In the second tournament, there are two sportsmen, and everyone can defeat another, depending on kind of sports.
In the third tournament, the third sportsman in the strongest in both kinds of sports, so he is the winner regardless of the scheme.
最近，伯兰举办了一场涉及 #cf_span[k] 种运动的锦标赛。Vasya 想通过下注赚钱。
锦标赛的赛制非常神秘，尚未完全公开。比赛依次进行，每场比赛由两名尚未被淘汰的运动员进行，比赛可以在任意一种 #cf_span[k] 种运动中进行。输者被淘汰，最后剩下的运动员成为冠军。此外，赛制可以是任意的，事先并不公开。
Vasya 知道每位运动员在每种运动中的实力。他认为实力更高的运动员总是获胜。
锦标赛每年举行一次，每年都会有一名新选手加入。第一届锦标赛只有一名运动员参加，第二届有两名运动员，依此类推。Vasya 已经观看了过去 #cf_span[n] 年的锦标赛。请帮他计算每届锦标赛中可能的冠军人数。
第一行包含两个整数 #cf_span[n] 和 #cf_span[k] (#cf_span[1 ≤ n ≤ 5·104], #cf_span[1 ≤ k ≤ 10]) —— 分别表示锦标赛的届数和运动种类数。
接下来的 #cf_span[n] 行，每行包含 #cf_span[k] 个整数 #cf_span[si1, si2, ..., sik] (#cf_span[1 ≤ sij ≤ 109])，其中 #cf_span[sij] 表示第 #cf_span[i] 位运动员在第 #cf_span[j] 种运动中的实力。实力更高的运动员总是获胜。保证对于任意一种运动，所有实力值互不相同。
对于每届 #cf_span[n] 个锦标赛，输出可能成为冠军的选手数量。
在第一个样例中：
第一屆锦标赛只有一位运动员，他就是冠军。
第二屆锦标赛有两位运动员，他们各自在某种运动中都能击败对方，结果取决于比赛的运动类型。
第三屆锦标赛中，第三位运动员在两种运动中的实力都是最强的，因此无论赛制如何，他都是冠军。
## Input
第一行包含两个整数 #cf_span[n] 和 #cf_span[k] (#cf_span[1 ≤ n ≤ 5·104], #cf_span[1 ≤ k ≤ 10]) —— 分别表示锦标赛的届数和运动种类数。接下来的 #cf_span[n] 行，每行包含 #cf_span[k] 个整数 #cf_span[si1, si2, ..., sik] (#cf_span[1 ≤ sij ≤ 109])，其中 #cf_span[sij] 表示第 #cf_span[i] 位运动员在第 #cf_span[j] 种运动中的实力。实力更高的运动员总是获胜。保证对于任意一种运动，所有实力值互不相同。
## Output
对于每届 #cf_span[n] 个锦标赛，输出可能成为冠军的选手数量。
[samples]
## Note
在第一个样例中：
第一屆锦标赛只有一位运动员，他就是冠军。
第二屆锦标赛有两位运动员，他们各自在某种运动中都能击败对方，结果取决于比赛的运动类型。
第三屆锦标赛中，第三位运动员在两种运动中的实力都是最强的，因此无论赛制如何，他都是冠军。
### Definitions
**1. Parameters and Data:**
* Let $n, k \in \mathbb{Z}^+$ denote the number of tournaments and the number of sport kinds, respectively.
* Let $S = \{1, 2, \dots, n\}$ be the set of all sportsmen indexed by their arrival.
* For each sportsman $i \in S$, let $\mathbf{s}_i = (s_{i,1}, s_{i,2}, \dots, s_{i,k}) \in \mathbb{Z}^k$ denote the power vector, where $s_{i,j}$ is the power of sportsman $i$ in sport $j$.
**2. Dominance Relation:**
For any two distinct sportsmen $u, v \in S$, we define the relation $u \to v$ ($u$ can defeat $v$) as:
$$ u \to v \iff \exists j \in \{1, \dots, k\} \text{ such that } s_{u,j} > s_{v,j} $$
*(Note: Since all powers in a specific sport are distinct, a match never results in a draw.)*
**3. Possible Winners Set:**
For a set of participants $P \subseteq S$, let $\mathcal{W}(P)$ denote the set of possible winners. This set is defined recursively:
* **Base Case:** If $|P| = 1$, then $\mathcal{W}(P) = P$.
* **Recursive Step:** If $|P| > 1$, then $w \in \mathcal{W}(P)$ if and only if there exists a partition of $P$ into two non-empty disjoint sets $A$ and $B$ ($P = A \cup B, A \cap B = \emptyset$) such that:
$$ \exists a \in \mathcal{W}(A), \exists b \in \mathcal{W}(B) \text{ such that } (w = a \land a \to b) \lor (w = b \land b \to a) $$
**4. Annual Participant Sets:**
For each year $m \in \{1, \dots, n\}$, let $P_m$ be the set of participants present in that tournament:
$$ P_m = \{1, 2, \dots, m\} $$
### Objective
For each $m$ from $1$ to $n$, calculate the cardinality of the set of possible winners:
$$ \text{Output}_m = |\mathcal{W}(P_m)| $$