19197번 - Work 스페셜 저지다국어

There are $N$ men and $M$ different working assignments for them. You are given a matrix $A$ in which $A_{i,j} = 1$ if $i$-th worker is qualified to complete $j$-th job, and $A_{i,j} = 0$ otherwise. A worker can be assigned to a job only if he is qualified to complete that job.

Your goal is to assign workers to jobs in such a way that the distribution of the amounts of jobs done by workers is as close as possible to uniform (in Euclidean metric). This means that the $N$-dimensional vector in which $i$-th element is the amount of jobs completed by $i$-th worker must be as close as possible to the $N$-dimensional vector in which each element is equal to the real number $M / N$.

An additional requirement is that each job which can be completed at all must be assigned to exactly one worker.

The first line of input contains two integers $N$ and $M$ ($1 \le N, M \le 300$). It is followed by $N$ lines each containing $M$ characters. Each of these characters is either '0' or '1'. These lines represent the matrix $A$.

Print $N$ lines. On $i$-th line, first, print $k_i$, the amount of jobs assigned to $i$-th worker. After that, print the numbers of those jobs. If there are several different ways to assign jobs and get an optimal distribution, print any one of them.

The Euclidean distance between two vectors $(u_1, u_2, \ldots, u_N)$ and $(v_1, v_2, \ldots, v_N)$ is the real number $$\sqrt{(v_1 - u_1)^2 + (v_2 - u_2)^2 + \ldots + (v_N - u_N)^2}\text{.}$$