Hungry Rabbit

时间限制:100s      空间限制:512MB

题目描述

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


输入格式

 

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


输出格式

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



样例输入

5 4 3 1
1001
1101
1111
1110
0111

样例输出

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

 

提示

对于 100% 的测试数据,1 <= n;m <= 800; 1 <= k <= n; 1 <= l <= k


题目来源

没有写明来源