Balanced Job Assignment

There are $N$ workers and $M$ different jobs. You are given a matrix $A$, where $A_{i,j}=1$ if worker $i$ is qualified to complete job $j$, and $A_{i,j}=0$ otherwise. A worker can be assigned to a job only if they are qualified for it.

Assign workers to jobs so that the distribution of the number of jobs done by each worker is as close as possible to uniform, measured by Euclidean distance. That is, the $N$-dimensional vector whose $i$-th element is the number of jobs done by worker $i$ should be as close as possible to the $N$-dimensional vector whose every element is the real number $M / N$.

Each job that can be completed by at least one worker must be assigned to exactly one worker.

The first line contains two integers $N$ and $M$ ($1 \le N, M \le 300$). The next $N$ lines each contain $M$ characters, either '0' or '1'. These lines describe the matrix $A$.

Print $N$ lines. On line $i$, first print $k_i$, the number of jobs assigned to worker $i$. Then print the numbers of those jobs. If several assignments give an optimal distribution, you may print any of them.

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