Distributing the Treasure

You are the leader of a treasure hunting team. Under your direction, the team succeeded in a quest and obtained a lot of treasure. The only remaining issue is how to distribute the treasure among the team members, and it matters.

The treasure includes a variety of precious items: gold ingots, jewelry with brilliant gemstones, exquisite craft works, and so on. Each team member estimates the values of the items individually. The estimates are consistent: for any pair of items, if some member estimates one strictly higher than the other, no member estimates the opposite. Some members may give equal estimates.

All members are sensible and understand that the items cannot be divided evenly. So no member gets angry merely because the sum of the values in their share, by their own estimate, is lower than another member's share. A member does get angry if their own share is estimated strictly lower than another member's share, even after removing the item with the least estimated value from that other share. Some members may receive nothing as long as they do not get angry.

Decide who receives which items so that no member gets angry.

The first line has two positive integers $n$ and $m$ with $n \times m \le 2 \times 10^5$. Here $n$ is the number of members and $m$ is the number of treasure items. Members and items are numbered 1 through $n$ and 1 through $m$.

The $i$-th of the following $n$ lines contains $m$ positive integers, each at most $2 \times 10^5$, in descending order: $v_{i,1} \ge v_{i,2} \ge \cdots \ge v_{i,m}$. Here $v_{i,j}$ is the value of item $j$ estimated by member $i$.

If the items can be distributed without making any member angry, output $m$ positive integers $x_1, x_2, \dots, x_m$ separated by spaces, where $x_j = i$ means member $i$ receives item $j$. If several distributions are valid, any of them is accepted.

If no distribution avoids anger, output 0 on a line.

Let $V_i(X)$ denote the sum of the values of the items in set $X$ as estimated by 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 output shows a distribution where member 1 is not angry, since $V_1(\{1, 3\}) \ge V_1(\{2\})$. Member 2 is not angry either, even though $V_2(\{2\}) < V_2(\{1, 3\})$. If member 1 gives up one of the two items, the remaining share would be worth $V_2(\{1\}) = 3$ or $V_2(\{3\}) = 3$, and neither is higher than $V_2(\{2\}) = 3$.

The shares cannot be swapped. Suppose member 1 receives $\{2\}$ and member 2 receives $\{1, 3\}$. Member 1 is angry because $V_1(\{2\}) = 2 < 4 = V_1(\{1\})$. Even if member 2 gives up item 3, the lesser item in $\{1, 3\}$, the remaining item 1 is still estimated higher than $V_1(\{2\}) = 2$.

In Sample 2, you are the only member, so you take all the items.