Tournament
Contest: Codeforces Round 443 (Div. 1)
Difficulty rating: 2700
Tags: data structures, graphs

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 format:
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 si1, si2, ..., sik (1 ≤ sij ≤ 109), where sij 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 format:
For each of the n tournaments output the number of contenders who can win.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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.

Example input:
3 2
1 5
5 1
10 10

Example output:
1
2
1

Example input:
3 2
2 2
3 3
1 10

Example output:
1
1
3

Editorial:
Imagine a directed graph, in which the vertices are participants, and the edge means that one participant can win the other in some kind of sports. A participant can win a tournament if there is a directed tree in this graph that contains all vertices, and this player is a root.
Consider the condensation of this graph. Since for any two vertices there is an edge at least in one direction, condensation is a path. It is clear that the required tree exists if and only if the root lies in the first strongly connected component.
We will maintain these strongly connected components. For each of them we will store its size, the greatest power and the smallest power in each kind of sports.
What happens when the new sportsman is added? He can defeat the component if in some kind of sports he is stronger than the minimum in this component. Similarly, he can lose to a component if in some kind of sports he is weaker than the maximum in this component. We need to find the weakest of those components that he can lose, and the strongest of those components that he can defeat. If the first component is stronger than the second, the new sportsman forms a new component. Otherwise, all the components between the first and the second merge into one, and the new sportsman joins it.
How to do it effectively? We will store the components in a some search tree and use the comparison by minimum in the first kind of sports as a comparator. It's easy to see that if you take any other sport or replace a minimum with a maximum, any two components will be compared in the same way. All we need is binsearch by one of the mentioned comparators: minimum or maximum for one of the kinds of sports.
At each step the number of operations with the tree is O(k) + k· number of components merged into one. At each step at most one component can be added, so the amortized time of one step is $${\mathcal {O}}(\log n)$$.
Overall time complexity is $${ \mathcal { O } } ( n k \log n )$$.