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·10^5, 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.

Difficulty: MEDIUM_HARD
Tags: Greedy algorithms

Mathematics

Constructive algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
(n, a, b, k) = map(int, input().split())
open = 0
must = 0
must_arr = []
for (i, c) in enumerate(input()):
	if c == '1':
		open = 0
	else:
		open += 1
		if open == b:
			open = 0
			must += 1
			if must >= a:
				must_arr.append(i + 1)
must -= a - 1
print(must)
print(*must_arr)


def sum_zeroth(arr):
	res = 0
	for elem in arr:
		res += elem[0]
	return res
(n, a, b, k) = map(int, input().split())
data = input()
dist = []
pp = 0
last = 0
for i in range(n):
	if data[i] == '1':
		dist.append((last, i))
		pp += (i - last) // b
		last = i + 1
dist.append((last, n))
pp += (n - last) // b
pos = []
minp = pp - a + 1
fnd = False
for elem in dist:
	cur = elem[0] - 1
	while cur + b < elem[1]:
		cur += b
		pos.append(cur + 1)
		if len(pos) == minp:
			fnd = True
			break
	if fnd:
		break
print(minp)
print(' '.join(map(str, pos)))


from itertools import groupby
(n, a, b, k) = map(int, input().split())
s = input()
sg = [list(g) for (s, g) in groupby(s)]
ll = 0
hits = []
for i in range(0, len(sg)):
	if sg[i][0] == '0' and len(sg[i]) >= b:
		for hit in range(b - 1, len(sg[i]), b):
			hits.append(hit + ll + 1)
		ll += len(sg[i])
	else:
		ll += len(sg[i])
hits = hits[a - 1:]
print(len(hits))
print(*hits)


def modinv(n, p):
	return pow(n, p - 2, p)

def main():
	(n, a, b, k) = [int(x) for x in input().split()]
	ip = input()
	s = ip.split('1')
	segments = []
	indices = []
	possible = 0
	for x in s:
		if len(x) > 0:
			segments.append(len(x))
		possible += len(x) // b
	if ip[0] == '0':
		indices.append(1)
	for i in range(1, n):
		if ip[i] == '0' and ip[i - 1] == '1':
			indices.append(i + 1)
	rem = k
	ans = 0
	shots = []
	for i in range(len(segments)):
		ind = indices[i]
		x = segments[i]
		if possible - x // b >= a:
			ans += x // b
			possible -= x // b
			j = ind + (b - 1)
			for y in range(x // b):
				shots.append(j)
				j += b
		else:
			j = ind + (b - 1)
			while possible - a >= 0:
				shots.append(j)
				j += b
				possible -= 1
				ans += 1
	print(ans)
	print(*shots)
py2 = round(0.5)
if py2:
	from future_builtins import ascii, filter, hex, map, oct, zip
	range = xrange
import os, sys
from io import IOBase, BytesIO
BUFSIZE = 8192

class FastIO(BytesIO):
	newlines = 0

	def __init__(self, file):
		self._file = file
		self._fd = file.fileno()
		self.writable = 'x' in file.mode or 'w' in file.mode
		self.write = super(FastIO, self).write if self.writable else None

	def _fill(self):
		s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
		self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
		return s

	def read(self):
		while self._fill():
			pass
		return super(FastIO, self).read()

	def readline(self):
		while self.newlines == 0:
			s = self._fill()
			self.newlines = s.count(b'\n') + (not s)
		self.newlines -= 1
		return super(FastIO, self).readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.getvalue())
			(self.truncate(0), self.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		if py2:
			self.write = self.buffer.write
			self.read = self.buffer.read
			self.readline = self.buffer.readline
		else:
			self.write = lambda s: self.buffer.write(s.encode('ascii'))
			self.read = lambda : self.buffer.read().decode('ascii')
			self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import heapq
from itertools import groupby

def read_int():
	return int(input().strip())

def read_ints():
	return list(map(int, input().strip().split(' ')))

def ilen(ll):
	return sum((1 for _ in ll))

def solve():
	(n, a, b, k) = read_ints()
	s = input().strip()
	segments = []
	maximum_count = 0
	for (start, vals) in groupby(enumerate(s), key=lambda p: p[1]):
		val = next(vals)
		if val[1] == '0':
			segments.append((val[0], 1 + ilen(vals)))
			maximum_count += segments[-1][1] // b
	shots = []
	while maximum_count >= a:
		(start, length) = segments.pop()
		if length // b > 0:
			shots.append(start + b - 1)
			segments.append((start + b, length - b))
			maximum_count -= 1
	print(len(shots))
	print(' '.join(map(lambda shot: str(shot + 1), shots)))
solve()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 10 ** 9 + 7
Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()
(n, a, b, k) = Ri()
s = ri()
cnt = 0
totans = 0
ans = []
for i in range(len(s)):
	if s[i] == '0':
		cnt += 1
	else:
		cnt = 0
	if cnt == b:
		if a > 1:
			a -= 1
		else:
			ans.append(i + 1)
			totans += 1
		cnt = 0
print(totans)
print(*ans)


(n, a, b, k) = [int(i) for i in input().split()]
s = input()
l = []
i = 0
j = 0
while i < len(s):
	if s[i] == '1':
		j = 0
	else:
		j += 1
		if j % b == 0:
			l += [i + 1]
			j = 0
	i += 1
l = l[a - 1:]
print(len(l))
print(*l)


(n, a, b, k) = map(int, input().split())
s = input()
ind = 0
ans = []
for i in range(k):
	l = s[ind:].find('1')
	if l >= b:
		ans.append([l, ind, ind + l])
	ind += l + 1
if len(s) - ind >= b:
	ans.append([len(s) - ind, ind, len(s)])
aans = []
count = 0
for i in range(len(ans)):
	j = ans[i][1] - 1
	while j + b < ans[i][2]:
		j += b
		aans.append(j + 1)
l = len(aans) - a + 1
aans = aans[:l]
print(len(aans))
print(*aans)


import os
import sys
from io import BytesIO, IOBase
import math
from collections import Counter
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def lcm(a, b):
	return a * b / gcd(a, b)

def main():
	(n, a, b, k) = map(int, input().split())
	s = input()
	a1 = [0] * n
	for i in range(n):
		if s[i] == '1':
			a1[i] = 1
	ans = []
	now = 0
	for i in range(n):
		if a1[i] == 1:
			now = 0
		else:
			now += 1
		if now == b:
			ans.append(i)
			now = 0
	print(len(ans) - a + 1)
	for i in range(len(ans) - a + 1):
		print(ans[i] + 1, end=' ')
	return
main()


(n, a, b, k) = map(int, input().split())
A = input()
B = A.split('1')
C = []
l = 1
for i in B:
	if len(i) >= b:
		for j in range(b - 1, len(i), b):
			C.append(j + l)
	l += len(i) + 1
C = C[:len(C) - a + 1]
print(len(C))
print(' '.join(list(map(str, C))))


from sys import stdin
import collections
import math

def get_working(string):
	aux = []
	first = None
	if string[0] == 1:
		pass
	else:
		first = -1
	for i in range(len(string)):
		if string[i] == '1':
			if first == None:
				first = i
			elif first != None:
				aux.append([first, i, i - first - 1])
				first = i
	if first != None:
		aux.append([first, len(string), len(string) - first - 1])
	return aux
(n, a, b, k) = list(map(int, stdin.readline().split()))
string = list(stdin.readline().strip())
ans = 0
working = get_working(string)
current = a
flag = 0
for i in working:
	if flag == 1:
		break
	(start, end, gap) = i
	j = end - 1
	if gap // b > 0:
		while j > start:
			if current == 0:
				flag = 1
				break
			if (j - start) // b > 0:
				for k in range(j, j - b, -1):
					string[k] = '2'
				j -= b
				current -= 1
			else:
				break
ans = []
count = 0
for i in range(len(string)):
	if string[i] == '0':
		if i > 0 and string[i - 1] == '0':
			count += 1
		else:
			count = 1
		if count == b:
			string[i] = 'b'
			ans.append(i + 1)
			count = 0
for i in range(len(string)):
	if string[i] == '2':
		ans.append(i + 1)
		break
print(len(ans))
print(*ans)


from collections import deque
(n, a, b, k) = map(int, input().split())
s = input()
start = False
cnt = 0
arr = []
idx = -1
for i in range(n):
	if s[i] == '0':
		if start:
			cnt += 1
		else:
			start = True
			idx = i
			cnt = 1
	elif start:
		start = False
		arr.append([cnt, idx])
		cnt = 0
if cnt:
	arr.append([cnt, idx])
divides = deque([])
for i in range(len(arr)):
	if arr[i][0] % b == 0:
		divides.append(arr[i])
	else:
		divides.appendleft(arr[i])
pos = 0
while a != 1:
	if divides[pos][0] >= b:
		divides[pos][0] -= b
		divides[pos][1] += b
		a -= 1
	else:
		pos += 1
ans = 0
at = []
for i in range(len(arr)):
	if divides[i][0]:
		times = int(divides[i][0] // b)
		ans += times
		start = divides[i][1] + b - 1
		while times:
			at.append(start + 1)
			start += b
			times -= 1
print(ans)
print(*at)


(n, s, b, k) = map(int, input().split())
a = list('1' + input() + '1')
ans = []
cnt = 0
for i in range(len(a)):
	if a[i] == '0':
		cnt += 1
	else:
		cnt = 0
	if cnt == b:
		if s > 1:
			s -= 1
		else:
			ans.append(i)
		cnt = 0
print(len(ans))
for i in range(len(ans)):
	print(ans[i], end=' ')


(n, a, b, k) = map(int, input().split())
s = list(input())
n = len(s)
lz = []
zeros = []
indexes = []
flage = 0
if s[0] == '0':
	lz.append(0)
	flage = 1
for i in range(1, n):
	if flage == 1 and s[i] == '1':
		zeros.append(i - 1 - lz[-1] + 1)
		lz.append(i - 1)
		flage = 0
	elif flage == 0 and s[i] == '0':
		lz.append(i)
		flage = 1
if s[-1] == '0':
	zeros.append(n - 1 - lz[-1] + 1)
	lz.append(n - 1)
min_no_spaces = (a - 1) * b
spaces_left = n - k
l = len(lz)
shotes = 0
for i in range(len(zeros)):
	h = i * 2
	if min_no_spaces != 0:
		if min_no_spaces >= zeros[i]:
			min_no_spaces -= int(zeros[i] / b) * b
		elif min_no_spaces < zeros[i]:
			shotes += int((zeros[i] - min_no_spaces) / b)
			for j in range(int((zeros[i] - min_no_spaces) / b)):
				indexes.append(lz[h] + (j + 1) * b)
			min_no_spaces = 0
	elif min_no_spaces == 0:
		shotes += int(zeros[i] / b)
		for j in range(int(zeros[i] / b)):
			indexes.append(lz[h] + (j + 1) * b)
print(shotes)
for i in indexes:
	print(i, ' ', end='', sep='')


(n, a, b, k) = list(map(int, input().split()))
s = input()
sm = 0
num = 0
res = []
for i in range(n):
	if s[i] == '1':
		sm = 0
	if s[i] == '0':
		sm += 1
		if sm == b:
			num += 1
			res.append(i + 1)
			sm = 0
k = num - a + 1
print(k)
print(*res[:k])


(n, a, b, k) = map(int, input().split())
A = ['1'] + list(input()) + ['1']
answer = []
n += 2
i = 0
while i <= n - 2:
	per = 0
	for j in range(i + 1, i + b + 1):
		if j > n - 1:
			break
		if A[j] == '1':
			i = j
			per = 1
			break
	if per == 0:
		i = j
		answer.append(i)
lens = len(answer)
print(lens - a + 1)
print(' '.join(map(str, answer[0:lens - a + 1])))