시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 256 MB 0 0 0 0.000%

문제

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.

예제 입력 1

3 3
111
111
111

예제 출력 1

1 1
1 2
1 3

예제 입력 2

2 4
0100
1100

예제 출력 2

1 2
1 1

노트

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{.}$$