24967번 - Distributing the Treasure 스페셜 저지다국어

문제

You are the leader of a treasure hunting team. Under your great direction, your team has made a big success in a quest, and got a lot of treasure. The only, but crucial, remaining issue is how to distribute the obtained treasure to the team members.

The excavated treasure includes a variety of precious items: gold ingots, jewelry with brilliant gem stones, exquisite craft works, etc. Each team member individually estimates the values of the items. The estimated values are consistent, in that, for any pair of two items, when some member estimates one to be strictly higher than the other, no member estimates oppositely, although some may give equal estimates.

All the members are sensible and thus understand the difficulty of even distribution of the items. Hence, no member will complain simply because, based on the member’s own estimation, the sum of the values of the member’s share is lower than that of another member’s share. The members, however, may get angry if their own shares look unreasonably shabby compared to some other member’s; what they cannot stand is when their own shares are estimated strictly lower than the share of that other member even after getting rid of one item with the least estimated value.

Your last mission as the leader is to decide who receives which items so that no member gets angry. Some of the members may receive nothing as long as they do not get angry.

입력

The input consists of a single test case of the following format.

$\begin{align*}& n ,円 m \\ & v_{1,1} ,円 \cdots ,円 v_{1, m} \\ & \vdots \\ & v_{n,1} ,円 \cdots ,円 v_{n,m} \end{align*}$

The first line of the input has two positive integers $n$ and $m$ whose product does not exceed 2ドル × 10^5$; $n$ is the number of members of your treasure hunting team, and $m$ is the number of treasure items. The members and items are numbered 1ドル$ through $n$ and 1ドル$ through $m,ドル respectively. The $i$-th of the following $n$ lines has $m$ positive integers not exceeding 2ドル × 10^5$ in descending order: $v_{i,1} ≥ v_{i,2} ≥ \cdots ≥ v_{i,m}$. Here, $v_{i,j}$ is the value of the item $j$ estimated by the member $i$.

출력

If you can distribute the items to the members without making any member angry, output such a distribution in a line as $m$ positive integers $x_1,ドル $x_2,ドル $\dots,ドル $x_m$ separated by spaces. Here, $x_j = i$ means that the member $i$ receives the item $j$. If two or more such distributions exist, any of them shall be deemed correct. If there is no way to distribute the items without making any member angry, just output 0 in a line.

제한

힌트

Let $V_i(X)$ denote the sum of the values of items in the set $X$ estimated by the member $i$.

In Sample 1, $V_1(\{1, 3\})$ is 4ドル + 1 = 5,ドル $V_1(\{2\})$ is 2ドル,ドル $V_2(\{1, 3\})$ is 3ドル + 3 = 6,ドル and $V_2(\{2\})$ is 3ドル$. The distribution shown as output does not make the member 1ドル$ angry as $V_1(\{1, 3\}) ≥ V_1(\{2\})$. The member 2ドル$ does not get angry either even though $V_2(\{2\}) < V_2(\{1, 3\})$ holds. If the member 1ドル$ waives one of the two items, the sum of the values of items received by the member 1ドル$ would become $V_2(\{1\}) = 3$ or $V_2(\{3\}) = 3,ドル neither of which is higher than $V_2(\{2\}) = 3$.

Note that their shares should not be exchanged. Suppose that the member 1ドル$ receives $\{2\}$ and the member 2ドル$ receives $\{1, 3\}$. This makes the member 1ドル$ angry because $V_1(\{2\}) = 2 < 4 = V_1(\{1\})$ holds, meaning that, even if the member 2ドル$ waives the item 3ドル,ドル which is estimated to be the lesser of $\{1, 3\},ドル the value of the sole remaining item 1ドル$ is still estimated higher than $V_1(\{2\}) = 2$.

In Sample 2, you are the sole member of your team, so you can take them all. Congratulations!