P3895 [Hunan Training Camp] Hungry Rabbit

A terrible flood struck unexpectedly in the summer, and the Rabbit Kingdom suffered an unprecedented famine. They have to go to the forest to look for food. For simplicity, suppose there are $n$ rabbits in the kingdom, numbered $1$ to $n$. During the $m$ days before relief arrives, exactly $k$ rabbits must go to the forest each day to gather food. Ferocious wolves live in the forest, but fortunately the rabbits have figured out the wolves’ hunting pattern: on each day, the wolves only hunt rabbits with certain indices. For safety, the $k$ rabbits sent out each day must all be ones that will not be hunted that day. Because the rabbits going out differ from day to day, they define for each day a newcomer count $p_i$: the number of rabbits that go out on day $i$ but did not go out on day $i - 1$. By convention, $p_1 = 0$. Now the rabbits want, under the safety requirement, that the newcomer count each day does not exceed $l$. Please construct a valid plan.

The first line contains four integers $n, m, k, l$. The next $n$ lines each contain a binary string of length $m$. In the $i$-th line, if the $j$-th character is $0$, then on day $j$ rabbit $i$ will be hunted; if it is $1$, then rabbit $i$ will not be hunted on that day.

Output $m$ lines. Each line should contain $k$ distinct integers between $1$ and $n$, representing the indices of the rabbits that go out to gather food on that day. If there is no valid plan, output a single line with -1.

Sample 1 Explanation For the sample, over the $4$ days, the sets of rabbits going out are respectively {2, 3, 4}; {2, 3, 4}; {3, 4, 5}; {2, 3, 5}. Constraints - For $20\%$ of the testdata, $1 \le n, m \le 10$. - For $100\%$ of the testdata, $1 \le n, m \le 800$, $1 \le k \le n$, $1 \le l \le k$. Translated by ChatGPT 5