#P3661. Hungry Rabbit

Hungry Rabbit

[湖南集训] Hungry Rabbit

题目描述

洪水过后,兔子王国粮食短缺。救济粮到来之前,编号为 11 至 nn 的兔子要在接下来的 mm 天里每天派恰好 kk 只去森林觅食。狼每天会捕食指定编号的兔子,当天出去的兔子必须全都安全。

记第 ii 天出去的兔子集合为 SiS_i。第 11 天的生疏度为 00。从第 22 天起,第 ii 天的生疏度为 ∣Si∖Si−1∣|S_i\setminus S_{i-1}|,即当天出去且前一天没有出去的兔子数。请构造一种方案,使每天的生疏度都不超过 ll。

输入格式

第一行有四个整数 n,m,k,ln,m,k,l。

接下来 nn 行,每行是长度为 mm 的 0101 串。第 ii 行第 jj 个字符为 0,表示狼在第 jj 天会捕食兔子 ii。字符为 1,表示兔子 ii 当天可以安全出去。

输出格式

若有合法方案,输出 mm 行。第 ii 行有 kk 个互不相同的整数,表示第 ii 天出去的兔子编号。输出任意一种合法方案即可。

若无解,输出一行 -1。

样例

5 4 3 1
1001
1101
1111
1110
0111
2 3 4
2 3 4
3 4 5
2 3 5

这四天的生疏度依次为 0,0,1,10,0,1,1。

数据范围

测试数据比例 n,mn,m
20%20\% 1≤n,m≤101\le n,m\le 10
100%100\% 1≤n,m≤8001\le n,m\le 800

所有测试数据均满足 1≤k≤n1\le k\le n、1≤l≤k1\le l\le k。