D. Sea Battle
time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Galya is playing one-dimensional Sea Battle on a 1 × n grid. In this game a ships are placed on the grid. Each of the ships consists of b consecutive cells. No cell can be part of two ships, however, the ships can touch each other.

Galya doesn't know the ships location. She can shoot to some cells and after each shot she is told if that cell was a part of some ship (this case is called "hit") or not (this case is called "miss").

Galya has already made k shots, all of them were misses.

Your task is to calculate the minimum number of cells such that if Galya shoot at all of them, she would hit at least one ship.

It is guaranteed that there is at least one valid ships placement.

Input

The first line contains four positive integers n, a, b, k (1 ≤ n ≤ 2·105, 1 ≤ a, b ≤ n, 0 ≤ k ≤ n - 1) — the length of the grid, the number of ships on the grid, the length of each ship and the number of shots Galya has already made.

The second line contains a string of length n, consisting of zeros and ones. If the i-th character is one, Galya has already made a shot to this cell. Otherwise, she hasn't. It is guaranteed that there are exactly k ones in this string.

Output

In the first line print the minimum number of cells such that if Galya shoot at all of them, she would hit at least one ship.

In the second line print the cells Galya should shoot at.

Each cell should be printed exactly once. You can print the cells in arbitrary order. The cells are numbered from 1 to n, starting from the left.

If there are multiple answers, you can print any of them.

Examples
Input
5 1 2 1
00100
Output
2
4 2
Input
13 3 2 3
1000000010001
Output
2
7 11
Note

There is one ship in the first sample. It can be either to the left or to the right from the shot Galya has already made (the "1" character). So, it is necessary to make two shots: one at the left part, and one at the right part.

/*
RE返回T我也是醉了.......
*/
/*
贪心先看海面上能撑下几艘船。然后只要打sum-a+1个点就能保证至少能达到一艘船
*/
#include <bits/stdc++.h>
using namespace std;
int main()
{
//freopen("C:\\Users\\acer\\Desktop\\in.txt","r",stdin);
int n,a,b,k;
char op[];
scanf("%d%d%d%d",&n,&a,&b,&k);
scanf("%s",op+);
//cout<<op<<endl;
vector<int>v;
int l=;
for(int i=;i<=n;i++){
//cout<<op[i];
if(op[i]==''){
l=i;
}
if(i-l==b){
v.push_back(i);
l=i;
}
}
//cout<<endl;
printf("%d\n",v.size()-a+);
for(int i=;i<v.size()-a+;i++)
printf(i?" %d":"%d",v[i]);
return ;
}

最新文章

  1. 内省、JavaBean、PropertyDescriptor类、Introspector类、BeanUtils工具包、注解、Rentention、Target、注解的基本属性和高级属性
  2. HDU-敌兵布阵
  3. bind,unbing,on,live,delegate绑定和解绑事件
  4. IIS6 + PHP 访问页面出现:需要进行身份验证的问题
  5. windows线程同步
  6. android 文件的权限
  7. C#基础知识-对象初始化顺序
  8. webapp设计注意事项
  9. 总结FormsAuthentication的使用
  10. GDAL的安装和配置(编译proj.4)
  11. [leetcode-605-Can Place Flowers]
  12. ASCII,Unicode 和 UTF-8
  13. centos 进程查看
  14. A1280. 最长双回文串
  15. samba服务配置(二)
  16. 惊艳,Dubbo域名已改,也不再局限于Java!
  17. Android Studio 运行出现 Multiple dex files define Landroid/support/annotation/AnimRes 解决方法
  18. Java 中各种空(&quot;&quot;、\u0000、null)的区别?
  19. ubuntu下安装、破解securtCRT工具
  20. SpringBoot使用JSP渲染页面

热门文章

  1. StringBuffer的替换和反转和截取功能
  2. node.js express mvc轻量级框架实践
  3. oracle 角色
  4. SpringBoot文档翻译系列——26.日志logging
  5. Hive简记
  6. hdu 5952 连通子图
  7. EnCase missed some usb activities in the evidence files
  8. java 学习笔记——类之间的关系之封装、继承与多态的详解
  9. SQLserver2008r2安装过程
  10. Are We There Yet? (zoj1745)