← 返回题目列表

Codeforces · 729/D

D. 海战

中文机器翻译题面 查看原题

Galya 正在 1 × n 网格上玩一维海战。在这个游戏中,一艘船被放置在网格上。每艘船都由 b 个连续的单元组成。任何细胞都不能成为两艘船的一部分,但是两艘船可以相互接触。

加利亚不知道船只的位置。她可以向一些细胞射击,每次射击后,她都会被告知该细胞是否是某艘船的一部分(这种情况称为“命中”)或不是(这种情况称为“未击中”)。

加利亚已经投了 k 次球,全部未命中。

你的任务是计算最少的单元格数量,这样如果加莉亚向所有单元格射击,她将击中至少一艘船。

保证至少有一艘有效的船舶放置。

输入

第一行包含四个正整数 n, a, b, k (1 ≤ n ≤ 2·105, 1 ≤ a, b ≤ n, 0 ≤ k ≤ n - 1) — 网格长度、网格上的船只数量、每艘船只的长度以及 Galya 已经射击的数量。

第二行包含一个长度为 n 的字符串,由 0 和 1 组成。如果第 i 个角色是一个,则 Galya 已经对该单元格进行了射击。否则,她还没有。保证该字符串中恰好有 k 个。

输出

在第一行中打印最小数量的单元格,这样如果 Galya 向所有单元格射击,她将击中至少一艘船。

在第二行打印 Galya 应该射击的单元格。

每个单元格都应该打印一次。您可以按任意顺序打印单元格。单元格从左侧开始编号为 1 到 n。

如果有多个答案,您可以打印其中任何一个。

示例

输入 #1

5 1 2 1
00100

输出 #1

2
4 2

输入 #2

13 3 2 3
1000000010001

输出 #2

2
7 11

注意

第一个样本中有一艘船。它可以位于 Galya 已经拍摄的镜头(“1”字符)的左侧或右侧。因此,需要进行两次拍摄:一次在左侧,一次在右侧。