토너먼트

최근 베를란드에서 k가지 종목의 토너먼트가 시작되었다. 바샤는 내기로 돈을 벌고 싶어 한다.

토너먼트의 진행 방식은 매우 불가사의하며 완전히 공개되지 않았다. 경기는 연달아 열리며, 각 경기에는 아직 토너먼트를 떠나지 않은 두 선수가 참가한다. 각 경기는 k가지 종목 중 어느 종목으로든 치를 수 있다. 패자는 토너먼트를 떠난다. 마지막까지 남은 선수가 우승자가 된다. 이 점을 제외하면 진행 방식은 임의로 정할 수 있으며, 사전에 공개되지 않는다.

바샤는 각 종목에서 선수들의 실력을 알고 있다. 그는 실력이 더 높은 선수가 항상 이긴다고 믿는다.

토너먼트는 매년 열리며, 해마다 새로운 참가자 한 명이 참가한다. 첫 토너먼트에는 선수 한 명만 참가했고, 두 번째 토너먼트에는 선수 두 명이 참가했으며, 이런 식으로 이어진다. 바샤는 지난 n년 동안 토너먼트를 지켜보았다. n개의 각 토너먼트에서 가능한 우승자의 수를 구하도록 도와주자.

첫째 줄에 정수 n와 k (1 ≤ n ≤ 5·104, 1 ≤ k ≤ 10)이 주어진다. 각각 토너먼트의 수와 종목의 수를 나타낸다.

다음 n개의 각 줄에는 k개의 정수 si1, si2, ..., sik (1 ≤ sij ≤ 109)가 주어진다. 여기서 sij는 i-th번째 선수의 j-th번째 종목에서의 실력이다. 실력이 더 높은 선수가 항상 이긴다. 모든 종목에서 선수들의 실력이 모두 서로 다름이 보장된다.

n개의 각 토너먼트에 대해 우승할 수 있는 선수의 수를 출력한다.

첫 번째 예제에서는 다음과 같다.

첫 토너먼트에는 선수 한 명만 있으며, 그 선수가 우승자이다.

두 번째 토너먼트에는 선수 두 명이 있으며, 종목에 따라 어느 선수든 다른 선수를 이길 수 있다.

세 번째 토너먼트에서는 세 번째 선수가 두 종목 모두에서 가장 강하므로, 진행 방식과 관계없이 그 선수가 우승자이다.