8606: Reviewer Assignment

gispzjz likes playing DotA2 and has recently become the chair of the celebrated conference SODA (Symposium on DotA2) in the community of DotA2, which focuses on research topics related to the design and analysis of strategies in DotA2 gaming.

Now the deadline for the Call For Papers of the 2023 Symposium on DotA2 has passed, and gispzjz has received a huge amount of papers! Fortunately, there are also many reviewers for the SODA conference, and gispzjz's job is to assign the papers to the reviewers for review. However, as there may be conflicts between paper writers and reviewers, each reviewer is only allowed to review a certain subset of the papers. Also, to avoid putting too much work on each reviewer, gispzjz should assign exactly one paper to each reviewer, while each paper is allowed to be reviewed by multiple or even no reviewers.

As the conference chair, gispzjz wants each paper to be fairly reviewed, so he wants to assign papers to reviewers such that the number of papers reviewed at least once is maximized, and under that constraint, the number of papers reviewed at least twice is maximized, then under both previous constraints, the number of papers reviewed at least three times is maximized, et cetera. Surely gispzjz would easily come up with the optimal assignment, but he just went to play DotA2 and left the problem for you.

The first line of input contains two integers n,m(1≤n,m≤400), denoting the number of reviewers and papers, respectively.
Then n lines follow, each line containing a string of length m consisting of $0$s and 1s, where the j(1≤j≤m)-th character of the i(1≤i≤n)-th string is 1 if the i-th reviewer is allowed to review the $j$-th paper, and isn't otherwise.

If there is no way to assign the papers to the reviewers such that each reviewer receives exactly one paper, output −1 in a line. Otherwise, output a line with $n$ integers a₁,a₂,…,a_n(1≤a_i≤m), denoting the a_i-th paper is assigned to the $i$-th reviewer in the optimal assignment. If there are more than one optimal assignment, outputting any of them is considered as correct.

3 3
111
110
100

3 2 1

For the third sample test, 2 2 3 3 1 is also a valid output.