Problem:
 Score : 600 points    Problem Statement Takahashi is playing a board game called Sugoroku.  On the board, there are N + 1 squares numbered 0 to N . Takahashi starts at Square 0 , and he has to stop exactly at Square N to win the game.  The game uses a roulette with the M numbers from 1 to M . In each turn, Takahashi spins the roulette. If the number x comes up when he is at Square s , he moves to Square s+x . If this makes him go beyond Square N , he loses the game.  Additionally, some of the squares are Game Over Squares. He also loses the game if he stops at one of those squares. You are given a string S of length N + 1 , representing which squares are Game Over Squares. For each i  (0 \leq i \leq N) , Square i is a Game Over Square if S[i] = 1 and not if S[i] = 0 .  Find the sequence of numbers coming up in the roulette in which Takahashi can win the game in the fewest number of turns possible. If there are multiple such sequences, find the lexicographically smallest such sequence. If Takahashi cannot win the game, print -1 .      Constraints  1 \leq N \leq 10^5  1 \leq M \leq 10^5  |S| = N + 1  S consists of 0 and 1 .  S[0] =  0  S[N] =  0         Input Input is given from Standard Input in the following format:  N  M  S       Output If Takahashi can win the game, print the lexicographically smallest sequence among the shortest sequences of numbers coming up in the roulette in which Takahashi can win the game, with spaces in between.  If Takahashi cannot win the game, print -1 .        Sample Input 1 9 3
0001000100      Sample Output 1 1 3 2 3  If the numbers 1 , 3 , 2 , 3 come up in this order, Takahashi can reach Square 9 via Square 1 , 4 , and 6 . He cannot reach Square 9 in three or fewer turns, and this is the lexicographically smallest sequence in which he reaches Square 9 in four turns.       Sample Input 2 5 4
011110      Sample Output 2 -1  Takahashi cannot reach Square 5 .       Sample Input 3 6 6
0101010      Sample Output 3 6

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
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 INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = MAP()
S = input()[::-1]

def check(a):
    for i in range(min(N, a+M), a, -1):
        if S[i] == '0':
            return i
    return a

i = 0
ans = []
while i < N:
    res = check(i)
    if res == i:
        print(-1)
        exit()
    ans.append(res-i)
    i = res
print(*ans[::-1])

Solution (Python):
N,M=map(int,input().split())
S=input()
r=[]
p=N
while p>0:
    try:
        n=p-max(0,p-M)-S[max(0,p-M):p].index('0')
    except:
        print(-1)
        exit()
    r.append(n)
    p-=n
print(*r[::-1])

Solution (Python):
n, m = map(int, input().split())
s = input()

ans = []

i = n
while i > 0:
    flag = 1
    for l in reversed(range(1, m+1)):
        ni = i - l
        if ni < 0:
            continue
        if s[ni] == '1':
            continue
        if s[ni] == '0':
            ans.append(l)
            i = ni
            flag = 0
            break
    if flag:
        print(-1)
        exit()

ans_ = []
for i in reversed(range(len(ans))):
    ans_.append(ans[i])
print(*ans_)

Solution (Python):
n,m = list(map(int, input().split()))
s = input()

able = True
turn = []
ptr = n
searched = 0
while ptr != 0:
  goto = 0
  for i in range(1+searched, m+1):
    if ptr - i == 0:
      goto = i
      break
    elif s[ptr-i] == '0':
      goto = i
  if goto == 0:
    able = False
    break
  else:
    turn.append(goto)
    ptr -= goto
    searched = m - goto


if able:
  while len(turn):
    print(turn.pop())
else:
  print(-1)

Solution (Python):
n,m=map(int,input().split())
s=input()
pos=n
p=n
tmp=n
ans=[]
while pos>0:
    q=p
    while pos-q<m and q>0:
        q-=1
        
        if s[q]=='0':
            tmp=q
    p=q
    
    if tmp>=pos:
        print(-1)
        exit(0)
    ans.append(pos-tmp)
    pos=tmp

for i in range(1,1+len(ans)):
    print(ans[-i],end=' ')

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,m=LI()
  s=S()

  ans=[]
  counter=1
  for x in s[1:]:
    if x=='0':
      if counter>m:
        return -1
      ans.append(counter)
      counter=1
    else:
      counter+=1

  ans.reverse()
  _ans=[]

  sm=0
  for x in ans:
    if sm+x>m:
      _ans.append(sm)
      sm=x
    else:
      sm+=x
  if sm>0:
    _ans.append(sm)

  _ans.reverse()
  return ' '.join([str(x) for x in _ans])



print(main())

Solution (Python):
n,m = map(int,input().split())
s = list(input())
s.reverse()

ans = []

i = 0
j = m
while i+j>i:
    if i+j >= n:
        ans.append(n-i)
        i = n
        break
    elif i == n:
        break
    elif s[i+j] == '1':
        j -= 1
    else:
        ans.append(j)
        i += j
        j = m

if i != n:
    print(-1)
else:
    ans.reverse()
    print(*ans)

Solution (Python):
N, M = map(int, input().split())
S = input()

ans = []
flg = 1
i = N
while i != 0:
    for j in range(min(M, i), 0, -1):
        if S[i-j] == '0':
            ans.append(j)
            i -= j
            break
    else:
        flg = -1
        i = 0
    

if flg == -1:
    print(flg)
else:
    ans.reverse()
    print(*ans)

Solution (Python):
N, M = map(int,input().split())
S = list(input())
S.reverse()
p = 0
ans = []
while p != N:
    hoge = 0
    for i in range(min(M,N-p),0,-1):
        if S[p + i] == '0':
            hoge = i
            break
    p += hoge
    if hoge == 0:
        print(-1)
        exit()
    ans.append(hoge)
print(*reversed(ans))

Solution (Python):
import queue
import math
import copy
"""
N = int(input())



A = []
for i in range(N):
	A.append(int(input()))

print(A)

"""
(N,M) = (int(i) for i in input().split(" "))
S = input()[::-1]
T = []
for s in S:
	if len(T)%2 == 0:
		if s == '0':
			T.append(1)
		else:
			T[-1]+=1
	else:
		if s== '1':
			T.append(1)
		else:
			T[-1]+=1
for i in range(1,len(T)):
	T[i] += T[i-1]

ans = []
cur = 0

tt = 0

while cur+M<N:
	cur += M
	while T[tt] <= cur:
		tt += 1
	if tt % 2 == 1:
		tt  -= 1
		st = M-cur+T[tt]-1
		if st == 0:
			ans = None
			break
		ans.append(st)
		cur = T[tt] - 1
	else:
		ans.append(M)
if ans != None and cur < N:
	ans.append(N-cur)
if ans == None:
	ans= [-1]
print(" ".join([str(i) for i in ans[::-1]]))

Solution (Python):
import sys
from bisect import bisect_left as bl
input = sys.stdin.readline

N, M = map(int, input().split())
S = list(input())[: -1]
x = N
res = []
s = []
for i in range(N + 1):
  if S[i] == "0": s.append(i)

for _ in range(N):
  if x == 0:
    break
  n = bl(s, x - M)
  
  res.append(x - s[n])
  x = s[n]
res.reverse()
if x != 0: print(-1)
else:
  print(" ".join(list(map(str, res))))

Solution (Python):

import sys, math, itertools, heapq, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**8)
inf = float('inf')
ans = count = 0

n,m=map(int,input().split())
S=input()
step=[]
def dfs(node):
    for i in range(m,0,-1):
        if node-i<0:
            continue
        
        if S[node-i]=="0":
            
            step.append(i)
            dfs(node-i)
            return

dfs(n)
step=step[::-1]
if sum(step)!=n:
    print(-1)
else:
    print(*step)

Solution (Python):
def main():
    n,m = map(int,input().split())
    s = list(input())
    sap = s.append
    _ = s.pop(-1)
    ans = []
    while True:
        x = []
        sl = len(s)
        xap = x.append
        f = False
        for i in range(m):
            if s:
                xap(s.pop(-1))
            else:
                f = True
                break
        if f:
            ans.append(sl)
            break
        lx = len(x)
        stop = 0
        g = False
        amari = []
        for i in range(lx):
            y = x.pop(-1)
            if y == "0":
                stop = m-i
                g = True
                break
            else:
                amari.append(y)
        if g:
            for i in range(len(amari)):
                sap(amari.pop(-1))
            ans.append(stop)
            if not s:
                break
        else:
            ans = -1
            break
    if ans == -1:
        print(ans)
    else:
        print(" ".join([str(i) for i in list(reversed(ans))]))
    
if __name__ == '__main__':
    main()

Solution (Python):
def main():
    N, M = map(int, input().split())
    S = input()[::-1]
    cur = 0
    i = 1
    ans = []
    while cur < N:
        cand = 0
        while i <= M and cur + i <= N:
            if S[cur + i] == "0":
                cand = i
            i += 1
        if cand == 0:
            print(-1)
            return
        ans.append(cand)
        i -= cand + 1
        cur += cand
    print(*ans[::-1])


if __name__ == "__main__":
    main()

Solution (Python):
class SegTree(object):
    
    
    
    
    
    __slots__ = ["elem_size", "tree", "default", "op"]
    def __init__(self, a: list, default=float("inf"), op=min):
        from math import ceil, log
        real_size = len(a)
        self.elem_size = elem_size = 1 << ceil(log(real_size, 2))
        self.tree = tree = [default] * (elem_size * 2)
        tree[elem_size:elem_size + real_size] = a
        self.default = default
        self.op = op
        for i in range(elem_size - 1, 0, -1):
            tree[i] = op(tree[i << 1], tree[(i << 1) + 1])

    def get_value(self, x: int, y: int) -> int:  
        l, r = x + self.elem_size, y + self.elem_size
        tree, result, op = self.tree, self.default, self.op
        while l < r:
            if l & 1:
                result = op(tree[l], result)
                l += 1
            if r & 1:
                r -= 1
                result = op(tree[r], result)
            l, r = l >> 1, r >> 1
        return result

    def get_threshold_left(self, x, y, v):
        
        tree, result, op, elem_size = self.tree, self.default, self.op, self.elem_size
        l, r = x + elem_size, y + elem_size
        idx_left = idx_right = -1  
        while l < r:
            if l & 1:
                result = op(tree[l], result)
                if idx_left == -1 and tree[l] <= v:
                    idx_left = l
                l += 1
            if r & 1:
                r -= 1
                result = op(tree[r], result)
                if tree[r] <= v:
                    idx_right = r
            l, r = l >> 1, r >> 1
        if idx_left==idx_right==-1:
            return -1, -1
        idx = idx_left if idx_left!=-1 else idx_right
        while idx < elem_size:
            idx <<= 1
            if tree[idx] > v:
                idx += 1
        return tree[idx], idx-elem_size

    def get_threshold_left_all(self, v):
        
        tree, op, elem_size = self.tree, self.op, self.elem_size
        if tree[1] > v:
            return -1, -1
        idx = 1
        while idx < elem_size:
            idx <<= 1
            if tree[idx] > v:
                idx += 1
        return tree[idx], idx-elem_size

    def set_value(self, i: int, value: int) -> None:
        k = self.elem_size + i
        self.tree[k] = value
        self.update(k)

    def update(self, i: int) -> None:
        op, tree = self.op, self.tree
        while i > 1:
            i >>= 1
            tree[i] = op(tree[i << 1], tree[(i << 1) + 1])



N, M = map(int, input().split())
S = list(map(int, input()))
dp = [10**9] * (N+1)
seg = SegTree(dp)
from_ = [-10000000] * (N+1)
seg.set_value(0, 0)
for i, c in enumerate(S[1:], 1):
    if c==1:
        continue
    v, idx = seg.get_threshold_left(max(i-M, 0), i, 1000000)
    if v==-1:
        print(-1)
        exit()
    from_[i] = idx
    seg.set_value(i, v+1)
n = seg.tree[N + seg.elem_size]



Ans = []
v = N
while v != 0:
    v_ = from_[v]
    Ans.append(v-v_)
    v = v_
Ans.reverse()
print(" ".join(map(str, Ans)))

Solution (Python):
from bisect import bisect_left, bisect_right

N, M = map(int, input().split())
Ss = input()

OKs = []
for i, S in enumerate(Ss):
    if S == '0':
        OKs.append(i)


dp = [0] * (N+1)
for i in range(N+1):
    j = bisect_left(OKs, i-M)
    dp[i] = OKs[j]


anss = []
i = N
while True:
    iPrev = dp[i]
    if iPrev == i:
        anss = []
        break
    if iPrev < 0:
        iPrev = 0
    anss.append(i-iPrev)
    if iPrev == 0:
        break
    i = iPrev

if not anss:
    print(-1)
else:
    print(' '.join(map(str, anss[::-1])))

Solution (Python):
class segment_tree_dual:
    def __init__(self, N, compose, funcval, ID_M=None):
        self.compose = compose
        self.ID_M = ID_M
        self.funcval = funcval

        self.height = (N-1).bit_length() 
        self.N0 = 1<<self.height 
        self.laz = [self.ID_M]*(2*self.N0) 
        self.val = None 

    
    def build(self,initial):
        self.val = initial[:]

    
    def propagate(self,k):
        if self.laz[k] == self.ID_M: return;
        if self.N0 <= k:
            self.val[k-self.N0] = self.funcval(self.val[k-self.N0], self.laz[k])
            self.laz[k] = self.ID_M
        else:
            self.laz[(k<<1)  ] = self.compose(self.laz[(k<<1)  ],self.laz[k]);
            self.laz[(k<<1)+1] = self.compose(self.laz[(k<<1)+1],self.laz[k]);
            self.laz[k] = self.ID_M;
    
    
    def propagate_all(self):
        upto = self.N0 + len(self.val)
        for i in range(1,upto): self.propagate(i)

    
    def thrust(self,k):
        for i in range(self.height,-1,-1): self.propagate(k>>i)

    
    def update(self, L,R,f):
        L += self.N0; R += self.N0+1
        """まず伝播させる（オペレータが可換なら必要ない）"""
        
        
        
        while L < R:
            if R & 1:
                R -= 1
                self.laz[R] = self.compose(self.laz[R],f)
            if L & 1:
                self.laz[L] = self.compose(self.laz[L],f)
                L += 1
            L >>= 1; R >>= 1
    
    
    def point_get(self, k):
        res = self.val[k]
        k += self.N0
        while k:
            if self.laz[k] != self.ID_M:
                res = self.funcval(res, self.laz[k])
            k //= 2
        return res
    
    
    def point_set(self, k): 
        self.thrust(k+self.N0)
        self.val[k] = x




import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
 
n,m = [int(i) for i in readline().split()]
s = input()[::-1]


compose = min
funcval = min
ID_M = INF = 10**18

seg = segment_tree_dual(n+1, compose, funcval, ID_M)
seg.build([0]+[INF]*(n))

for i in range(n):
    if s[i] == "1": seg.val[i] = -1
    else:
        v = seg.point_get(i)
        
        seg.update(i+1,min(n,i+m),v+1)
        

seg.propagate_all()



val = seg.val
if val[-1] == -1 or val[-1] == INF:
    print(-1)
    exit()

ans = []

now = n
time = val[-1]
while now:
    n2 = now-1
    time -= 1
    while s[n2] == "1" or val[n2] != time:
        n2 -= 1
    ans.append(now-n2)
    now = n2
    
print(*ans)

Solution (Python):
N, M = map(int, input().split())
s = input() 

N += 1

tree = [0] * (2 * N);  
n = N

def build() : 
  
    
    for i in range(N) :  
        tree[n + i] = (float('inf'), float('inf'));  
      
    
    for i in range(n - 1, 0, -1) :  
        tree[i] = min(tree[i << 1], tree[i << 1 | 1])
  

def updateTreeNode(p, value) :  
      
    
    tree[p + n] = (value, p);  
    p = p + n;  
      
    
    i = p; 
      
    while i > 1 : 
          
        tree[i >> 1] = min(tree[i], tree[i ^ 1]);  
        i >>= 1;  
  

def query(l, r) :  
  
    res = (float('inf'), float('inf'));  
      
    
    l += n; 
    r += n; 
      
    while l < r : 
      
        if (l & 1) : 
            res = min(res, tree[l]);  
            l += 1
      
        if (r & 1) : 
            r -= 1; 
            res = min(res, tree[r]);  
              
        l >>= 1; 
        r >>= 1
      
    return res;

par = [None for i in range(N)]
build()
updateTreeNode(0, 0)
for i in range(1, N):
    if s[i] == "1": continue
    r = query(max(0, i - M), i)
    par[i] = r[1]
    updateTreeNode(i, r[0]+1)
    
    
    
    
    



moves = []
cur = N - 1
if par[cur] == float('inf'):
    print(-1)
    quit()
try:
    while par[cur] != None:
        new = par[cur]
        moves.append(cur - new)
        cur = new
except:
    print(-1)
    quit()

moves = list(reversed(moves))
print(" ".join(map(str, moves)))

Solution (Python):

"""
演算子は要素とセットでモノイドを形成するようなものでなければならない。
すなわち、結合律が成り立ち単位元が存在する必要がある。

equalityはsetを高速化するために使う。めんどい場合はNoneにしてもOK
"""
class SegmentTree:

    @classmethod
    def all_identity(cls, operator, equality, identity, size):
        return cls(operator, equality, identity, [identity]*(2 << (size-1).bit_length()))

    @classmethod
    def from_initial_data(cls, operator, equality, identity, data):
        size = 1 << (len(data)-1).bit_length()
        temp = [identity]*(2*size)
        temp[size:size+len(data)] = data
        data = temp

        for i in reversed(range(size)):
            data[i] = operator(data[2*i],data[2*i+1])
        return cls(operator, equality, identity, data)

    
    def __init__(self, operator, equality, identity, data):
        if equality is None:
            equality = lambda a,b: False
        self.op = operator
        self.eq = equality
        self.id = identity
        self.data = data
        self.size = len(data)//2

    def _interval(self, a, b):
        a += self.size
        b += self.size
        ra = self.id
        rb = self.id

        data = self.data
        op = self.op
        while a < b:
            if a & 1:
                ra = op(ra,data[a])
                a += 1
            if b & 1:
                b -= 1
                rb = op(data[b],rb)
            a >>= 1
            b >>= 1
        return op(ra,rb)

    def __getitem__(self, i):
        if isinstance(i, slice):
            return self._interval(
                                    0 if i.start is None else i.start,
                                    self.size if i.stop is None else i.stop)
        elif isinstance(i, int):
            return self.data[i+self.size]

    def __setitem__(self, i, v):
        i += self.size
        data = self.data
        op = self.op
        eq = self.eq
        while i and not eq(data[i],v):
            data[i] = v
            v = op(data[i^1],v) if i & 1 else op(v,data[i^1])
            i >>= 1

    def __iter__(self):
        return iter(self.data[self.size:])

from operator import eq

N,M = map(int,input().split())
N += 1
S = tuple(map(lambda x: x == '0', input()))

dp = SegmentTree.all_identity(min, eq, float('inf'), N)
dp[N-1] = 0

for i in reversed(range(N-1)):
    if S[i]:
        dp[i] = dp[i+1:min(N,i+M+1)]+1
if dp[0] == float('inf'):
    print(-1)
    exit()

res = []
i = 0
while i < N-1:
    t = dp[i]
    k = 1
    while dp[i+k] != t-1:
        k += 1
    res.append(k)
    i += k
print(*res)

Solution (Python):




def main():
  _, m = map(int, input().split())
  traps = [v == '1' for v in input().strip()]
  values = [None] * len(traps)
  values[0] = -1

  for i in range(len(values) - 1):
    if values[i] is None:
      continue

    for j in range(min(i + m, len(values) - 1), i, -1):
      if j >= len(values) or traps[j]:
        continue

      if values[j] is not None:
        break

      values[j] = i

  if values[-1] is None:
    print(-1)
    return

  index = len(values) - 1
  route = []

  while values[index] != -1:
    route.append(index - values[index])
    index = values[index]

  print(' '.join(str(v) for v in route[::-1]))


if __name__ == '__main__':
  main()

Solution (Python):
import sys
import math
MAX_INT = int(10e15)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N, M = IL()
s = S()[::-1]

ans = []

now = 0
while True:
  if 0 <= now + M <= N:
    for num in range(1,M+1)[::-1]:
      if s[now + num] == "1":
        continue
      else:
        ans.append(num)
        now += num
        break
    else:
      print(-1)
      exit()
    continue
  else:
    if N - now == 0:
      pass
    else:
      ans.append(N - now)
    break

print(*ans[::-1])

Solution (Python):
import sys
n,m=map(int,input().split())
s=list(input())
s.reverse()
ans=[]
x=0
while x<n:
  f=0
  for i in range(x+1,min(x+1+m,n+1)):
    if s[i]=='0':
      y=i-x
      f=1
  if f==0:
    print(-1)
    sys.exit()
  ans.append(str(y))
  x+=y
ans.reverse()
print(' '.join(ans))

Solution (Python):
n,m=[int(j) for j in input().split()]
s=input()[::-1]
l=[]
for i in range(n+1):
    if s[i]=="0":
        l.append(i)
import bisect
ans=[]
c=0
while True:
    if c+m>=n:
        ans.append(n-c)
        break
    p=bisect.bisect_right(l,c+m)-1
    ans.append(l[p]-c)
    if l[p]-c==0:
        print(-1)
        exit()
    c=l[p]
    if c==n:
        break
print(*ans[::-1])

Solution (Python):
import sys
input = sys.stdin.readline



class RangeUpdateQuery:
    def __init__(self, n):
        self.n0 = 2**(n-1).bit_length()
        
        self.INF = float("inf")
        self.data = [self.INF]*(2*self.n0-1)

    
    
    
    def update(self, l,r,v):
        l += self.n0
        r += self.n0
        while l < r:
            if r&1:
                r -= 1
                if self.data[r-1] > v:
                    self.data[r-1] = v
            if l&1:
                if self.data[l-1] > v:
                    self.data[l-1] = v
                l += 1
            l >>=1
            r >>=1

    def query(self, i):
        i += self.n0-1
        res = self.INF
        while i+1:
            if self.data[i] < res:
                res = self.data[i]
            i = ~-i//2
        return res

n,m = map(int, input().split())
s = input()[:-1]
DP = [-1]*(n+1)
seg = RangeUpdateQuery(n+1)
seg.update(0,1,0)

ss = s[::-1]
for i in range(n):
    if ss[i] == "1":
        continue
    cnt = seg.query(i)
    if cnt == float("inf"):
        continue
    seg.update(i+1, min(i+m+1, n+1), cnt+1)

if seg.query(n) == float("inf"):
    print(-1)
    exit()
a = [seg.query(i) for i in reversed(range(n+1))]
for i in range(n+1):
    if s[i] == "1":
        a[i] = float("inf")

prev = a[0]
j = 0
ans = []
for i in range(n+1):
    if a[i]<prev:
        prev = a[i]
        ans.append(i-j)
        j = i
print(*ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,M=map(int,input().split())
    S=list(reversed(list(input())))
    i=0
    f=True
    l=[]
    while True:
        num=0
        for j in range(M):
            if i+(M-j) >= N:
                num=N-i
                break
            else:
                if S[i+(M-j)]=='0':
                    num=M-j
                    break
                else:
                    if j==M-1:
                        f=False
        l.append(str(num))
        i+=num
        if f==False:
            print(-1)
            exit()
        if i >= N:
            break
    print(' '.join(reversed(l)))

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    n,m=map(int,input().split())
    s=list(reversed(list(input())))
    cnt=0
    ans=[]
    while cnt<n:
        for i in range(min(m,n-cnt),0,-1):
            if s[cnt+i]=="0":
                cnt+=i
                ans.append(i)
                break
        else:
            print(-1)
            return 0
    print(*list(reversed(ans)))
main()

Solution (Python):
N,M = map(int,input().split())
S = input()

ans = []
i = N
while i > 0:
    for m in range(M,0,-1):
        if i-m <= 0:
            ans.append(i)
            i = 0
            break
        if S[i-m]=='0':
            ans.append(m)
            i -= m
            break
    else:
        print(-1)
        exit()
print(*ans[::-1])

Solution (Python):
N, M = map(int, input().split())
S = list(input())

n = N 
ans = []
while n != 0:
    for i in range(min(n, M), 0, -1):
        if S[n - i] == '0':
            n -= i
            ans.append(i)
            break
        if i == 1:
            print (-1)
            exit()

print (*ans[::-1])

Solution (Python):
N, M = map(int, input().split())
S_raw = input()

S = [0] * (N+1)
for i in range(N+1):
    if S_raw[i] == '1':
        S[N-i] = 1

left0 = list(range(N+1))
for i in range(1, N+1):
    if S[i] == 1:
        left0[i] = left0[i-1]

ans = []
i = 0
while True:
    if i + M >= N:
        ans.append(N - i)
        break
    j = left0[i + M]
    if j == i:
        print(-1)
        exit()
    ans.append(j-i)
    i = j

ans = reversed(ans)
print(*ans)

Solution (Python):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time

def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()

input=lambda: sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

n,m=LI()





def init(init_val):
    
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    
    for i in range(num-2,-1,-1) :
        seg[i]=min(seg[2*i+1],seg[2*i+2]) 

def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = min(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = min(res,seg[p])
        if q&1 == 1:
            res = min(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = min(res,seg[p])
    else:
        res = min(min(res,seg[p]),seg[q])
    return res


ide_ele = inf

ans=inf

s=[int(i) for i in input()]

def dp(b,m): 
    N=len(b)-1
    n=N+1
    global seg
    global num
    
    
    num =2**(n-1).bit_length()
    seg=[ide_ele]*2*num
    init([inf]*n)
    
    update(0,0)

    dp=[0]+[inf]*(N)
    for i in range(N):
        if b[i+1]==1:
            continue
        dp[i+1]=query(max(i-m+1,0),i+1)+1
        update(i+1,dp[i+1])
        
        
    return dp

dp1=dp(s,m)
step=dp1[n]
if step==inf:
    print(-1)
    exit()

dp2=dp(s[::-1],m)[::-1]

move=[0]
ans=[]
j=1
for i in range(step,0,-1): 
    while j<=n and dp2[j]!=i-1:
        j+=1
    
    move.append(j)


'''
show(s)
show(dp1,step)
show(dp2)
show(move)
'''

for i in range(len(move)-1):
    ans.append(move[i+1]-move[i])
print(*ans)

Solution (Python):
n,m = map(int,input().split())
s = list(input())

now = n
res = []

while now != 0:
    judge = False
    for i in range(max(0,now-m),now):
        if s[i] == '0':
            res.append(now-i)
            now = i
            judge = True
            break
    if not judge:
        print(-1)
        exit()
for i in range(len(res)-1,-1,-1):
    print(res[i],end = ' ')

Solution (Python):
n, m = [int(x) for x in input().split()]

s = input()
c = n

h = []
while True:
	d = m
	while d > 0:
		if c - d >= 0:
			if s[c - d] == '0':
				break
		d -= 1

	if d == 0:
		print(-1)
		break
	
	c -= d
	h.append(str(d))
	if c == 0:
		h.reverse()
		print(' '.join(h))
		break

Solution (Python):
import sys

N,M = map(int,input().split())

S = input()

slis = list(S)
slis.reverse()

ans = []

now = 0


while now != N:

    flag = False

    for i in range(M):
        i = M - i

        if now + i <= N and slis[now + i] == "0":
            flag = True
            now = now + i
            ans.append(i)
            break

    if not flag:
        print (-1)
        sys.exit()

ans.reverse()

print (" ".join(map(str,ans)))

Solution (Python):
n, m = map(int, input().split())
s = input()
if '1' * m in s:
    print(-1)
else:
    p = n
    t = []
    while p > 0:
        for r in range(m, 0, -1):
            if p - r >= 0 and s[p - r] == '0':
                t.append(r)
                p -= r
                break
    print(" ".join([str(r) for r in reversed(t)]))

Solution (Python):
n, m = [int(x) for x in input().split()]

s = input()
c = n

h = []
while True:
	d = m
	while d > 0:
		if c - d >= 0:
			if s[c - d] == '0':
				break
		d -= 1

	if d == 0:
		print(-1)
		break
	
	c -= d
	h.append(str(d))
	if c == 0:
		h.reverse()
		print(' '.join(h))
		break