Reviewer Assignment
题号:NC241126
时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

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 , denoting the number of reviewers and papers, respectively.

Then n lines follow, each line containing a string of length m consisting of 0s and 1s, where the -th character of the -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 , 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.
示例1

输入

复制
3 3
111
110
100

输出

复制
3 2 1
示例2

输入

复制
3 3
111
111
000

输出

复制
-1
示例3

输入

复制
5 3
010
010
101
011
100

输出

复制
2 2 1 3 1

备注:

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