[湖南集训] Hungry Rabbit

题目描述

可怕的洪水在夏天不期而至,兔子王国遭遇了前所未有的饥荒,它们不得不去外面的森林里寻找食物。 为了简化起见,我们假设兔子王国中有 $n$ 只兔子,编号为 $1$ 到 $n$。在救济粮到来之前的 $m$ 天中,每天恰好有 $k$ 只兔子需要去森林里寻找粮食。森林里居住着可怕的大灰狼,所幸兔子已经摸清了大灰狼捕食习惯,即狼们在每一天只会捕食特定编号的兔子。为了安全起见,兔子们需要保证每次出去觅食的 $k$ 只兔子都不会被狼捕食。 由于每天出去捕食的兔子都不尽相同,它们为每一天定义了一个生疏度 $p_i$ ,即第 $i$ 天出来寻找食物,但是第 $i−1$ 天却没有出来觅食的兔子个数。规定第 $1$ 天的生疏度为 $0$。 现在兔子们希望在保证安全的前提下,每天的生疏度不能超过 $l$,请为兔子们构造一个合法的方案。

输入输出格式

输入格式


第一行包括四个整数 $n, m, k, l$。 接下来 $n$ 行,每行一个长度为 $m$ 的 $01$ 串。其中第 $i$ 行第 $j$ 个字符若为 $0$,则表示狼在第 $j$ 天会捕食编号为 $i$ 的兔子,为 $1$ 则表示不捕食。

输出格式


共 $m$ 行,每行 $k$ 个 $1$ 到 $n$ 之间互不相同的整数,代表这一天出去寻找食物的兔子编号。 如果没有合法方案,则输出一行 `−1` 即可。

输入输出样例

输入样例 #1

5 4 3 1
1001
1101
1111
1110
0111

输出样例 #1

2 3 4
2 3 4
3 4 5
2 3 5

说明

#### 样例 1 解释 对于样例,在这 $4$ 天中,出去觅食的兔子集合分别为 $\{2, 3, 4\}; \{2, 3, 4\}; \{3, 4, 5\}; \{2, 3, 5\}$。 --- #### 数据规模与约定 - 对于 $20\%$ 的测试数据,保证 $1\leq n,m\leq 10$; - 对于 $100\%$ 的测试数据,保证 $1\leq n,m\leq 800,$,$1\leq k\leq n$,$1\leq l\leq k$。