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,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'

    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)
 
YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase

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

class Tree:
    def __init__(self,inp_size=None,ls=None,init=True,index=0):
        self.LCA_init_stat=False
        self.ETtable=[]
        if init:
            if ls==None:
                self.stdin(inp_size,index=index)
            else:
                self.size=len(ls)+1
                self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return
 
    def stdin(self,inp_size=None,index=1):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1,index=index)
        return
    
    def listin(self,ls,index=0):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return
 
    def __str__(self):
        return  str(self.edges)
 
    def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v
 
    def EulerTour(self,x):
        q=deque()
        q.append(x)
        self.depth=[None]*self.size
        self.depth[x]=0
        self.ETtable=[]
        self.ETdepth=[]
        self.ETin=[-1]*self.size
        self.ETout=[-1]*self.size
        cnt=0
        while q:
            c=q.pop()
            if c<0:
                ce=~c
            else:
                ce=c
                for nb,d in self.edges[ce]:
                    if self.depth[nb]==None:
                        q.append(~ce)
                        q.append(nb)
                        self.depth[nb]=self.depth[ce]+1
            self.ETtable.append(ce)
            self.ETdepth.append(self.depth[ce])
            if self.ETin[ce]==-1:
                self.ETin[ce]=cnt
            else:
                self.ETout[ce]=cnt
            cnt+=1
        return
    
    def LCA_init(self,root):
        self.EulerTour(root)
        
        self.st=SegTree(self.size*2-1,self.ETdepth,function=min,ide=inf)
        self.LCA_init_stat=True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.LCA_init(root)
        xin,xout=self.ETin[x],self.ETout[x]
        yin,yout=self.ETin[y],self.ETout[y]
        a=min(xin,yin)
        b=max(xout,yout,xin,yin)
        id_of_min_dep_in_et=self.st.query_id(a,b+1)
        return self.ETtable[id_of_min_dep_in_et]
 
class SparseTable: 
    def __init__(self,ls,init_func=min,init_idl=float('inf')):
        self.func=init_func
        self.idl=init_idl
        self.size=len(ls)
        self.N0=self.size.bit_length()
        self.table=[ls[:]]
        self.index=[list(range(self.size))]
        self.lg=[0]*(self.size+1)
        
        for i in range(2,self.size+1):
            self.lg[i]=self.lg[i>>1]+1
 
        for i in range(self.N0):
            tmp=[self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) for j in range(self.size)]
            tmp_id=[self.index[i][j] if self.table[i][j]==self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) else self.index[i][min(j+(1<<i),self.size-1)] for j in range(self.size)]
            self.table+=[tmp]
            self.index+=[tmp_id]
    
    
    def query(self,l,r):
        if r>self.size:r=self.size
        
        N=self.lg[r-l]
        return self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))])
    
    
    def query_id(self,l,r):
        if r>self.size:r=self.size
        
        N=self.lg[r-l]
        a,b=self.index[N][l],self.index[N][max(0,r-(1<<N))]
        if self.table[0][a]==self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))]):
            b=a
        return b
    
    def __str__(self):
        return str(self.table[0])
 
    def print(self):
        for i in self.table:
            print(*i)







class SegTree:
    def __init__(self,n,init_val=0,function=lambda a,b:a+b,ide=0):
        self.size=n
        self.ide_ele=ide
        self.num=1<<(self.size-1).bit_length()
        self.table=[self.ide_ele]*2*self.num
        self.index=[0]*2*self.num
        self.lazy=[self.ide_ele]*2*self.num
        self.func=function
        
        if not hasattr(init_val,"__iter__"):
            init_val=[init_val]*self.size
        for i,val in enumerate(init_val):
            self.table[i+self.num-1]=val
            self.index[i+self.num-1]=i
        
        for i in range(self.num-2,-1,-1):
            self.table[i]=self.func(self.table[2*i+1],self.table[2*i+2])
            if self.table[i]==self.table[i*2+1]:
                self.index[i]=self.index[i*2+1]
            else:
                self.index[i]=self.index[i*2+2]
        
    def update(self,k,x):
        k+=self.num-1
        self.table[k]=x
        while k:
            k=(k-1)//2
            res=self.func(self.table[k*2+1],self.table[k*2+2])
            self.table[k]=res
            if res==self.table[k*2+1]:
                self.index[k]=self.index[k*2+1]
            else:
                self.index[k]=self.index[k*2+2]
        
    def evaluate(k,l,r): 
        if lazy[k]!=0:
            node[k]+=lazy[k]
            if(r-l>1):
                lazy[2*k+1]+=lazy[k]//2
                lazy[2*k+2]+=lazy[k]//2

        lazy[k]=0
    
    def query(self,p,q):
        if q<=p:
            return self.ide_ele
        p+=self.num-1
        q+=self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1==0:
                res=self.func(res,self.table[p])
            if q&1==1:
                res=self.func(res,self.table[q])
                q-=1
            p=p>>1
            q=(q-1)>>1
        if p==q:
            res=self.func(res,self.table[p])
        else:
            res=self.func(self.func(res,self.table[p]),self.table[q])
        return res
    
    def query_id(self,p,q):
        if q<=p:
            return self.ide_ele
        p+=self.num-1
        q+=self.num-2
        res=self.ide_ele
        idx=p
        while q-p>1:
            if p&1==0:
                res=self.func(res,self.table[p])
                if res==self.table[p]:
                    idx=self.index[p]
            if q&1==1:
                res=self.func(res,self.table[q])
                if res==self.table[q]:
                    idx=self.index[q]
                q-=1
            p=p>>1
            q=(q-1)>>1
        if p==q:
            res=self.func(res,self.table[p])
            if res==self.table[p]:
                idx=self.index[p]
        else:
            res=self.func(self.func(res,self.table[p]),self.table[q])
            if res==self.table[p]:
                idx=self.index[p]
            elif res==self.table[q]:
                idx=self.index[q]
        return idx


    def __str__(self):
        
        rt=self.table[self.num-1:self.num-1+self.size]
        return str(rt)

show_flg=False
show_flg=True
ans=0

n,m=LI()
s=[int(i) for i in input()]
 
def dp(b,m): 
    N=len(b)-1
    n=N+1
    sg=SegTree(n,inf,min,inf)
 
    sg.update(0,0)
 
    dp=[0]+[inf]*(N)
    for i in range(N):
        if b[i+1]==1:
            continue
        dp[i+1]=sg.query(max(i-m+1,0),i+1)+1
        sg.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)
 
for i in range(len(move)-1):
    ans.append(move[i+1]-move[i])
print(*ans)
exit()

Solution (Python):
n,m=map(int,input().split())
s=list(map(int,list(input())))
ans=[]
i=n
while i>0:
  j=max(0,m-i)
  while s[i-(m-j)]!=0:
    j+=1
    if j==m:
      print(-1)
      exit(0)
  ans.append(m-j)
  i-=(m-j)
ans.reverse()
print(' '.join(map(str,ans)))

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**5 + 1
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N,M = LI()
    S = SI()
    N0 = 2 ** N.bit_length()
    st = [INF] * (2*N0)

    def update(i,x):
        i += N0-1
        st[i] = x
        while i > 0:
            i = (i-1) // 2
            st[i] = min(st[i*2+1], st[i*2+2])

    def query(l,r):
        L = l+N0; R = r+N0
        ret = INF
        while L < R:
            if L % 2:
                ret = min(ret,st[L-1])
                L += 1
            if R % 2:
                R -= 1
                ret = min(ret,st[R-1])
            L //= 2; R //= 2
        return ret

    update(0,0)

    for i in range(1,N+1):
        if S[i] == '1': continue
        else:
            if i <= M:
                update(i,1)
            else:
                x = query(i-M,i)
                update(i,x+1)
    if st[N+N0-1] >= INF:
        print(-1)
    else:
        ans = []
        f = N
        last_i = N
        s = st[N+N0-1]
        d = 1
        cnt = 0
        for i in range(N-1,-1,-1):
            cnt += 1
            if st[i+N0-1] == s-1:
                d = f - i
                last_i = i
            if cnt == M:
                ans.append(d)
                f = last_i
                s -= 1
                cnt = f - i
        if f > 0:
            ans.append(f)
        print(*reversed(ans),sep=' ')

if __name__ == '__main__':
    main()

Solution (Python):
n,m=map(int,input().split())
s=input()[::-1]
ans=[]
now=0
while(now<n):
  t=1
  for i in reversed(range(1,m+1)):
    if now+i>n or s[now+i]=='1':
        continue
    now=now+i
    ans.append(i)
    t=0
    break
  if t:
    print(-1)
    exit()
ans.reverse()
print(*ans,sep=' ')

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

p = N
ans = []
ans_ok = True
while True:
    if p <= M:
        ans.append(p)
        p -= p
        break
    check = False
    for i in range(M, 0, -1):
        if S[p-i] == '0':
            check = True
            ans.append(i)
            p -= i
            break
    if not check:
        ans_ok = False
        break
if ans_ok:
    print(' '.join(map(str, ans[::-1])))
else:
    print(-1)

Solution (Python):
n, m = map(int, input().split())
s = input()
dp = [-1 for _i in range(n+1)]
dp[0] = 0
f = 0
from collections import deque
q = deque([0])
c = 0
for i in range(1, n+1):
    if s[i]=="0":
        c = 0
        while i-f > m:
            f = q.popleft()
        dp[i] = f
        q.append(i)
    elif c < m-1:
        c += 1
    else:
        break

if dp[n] >= 0:
    r = []
    p = n
    while p > 0:
        nex = dp[p]
        r.append(p-nex)
        p = nex
    print(*r[::-1])
else:
    print(-1)

Solution (Python):
n, m = map(int, input().split())
s = input()
dp = [-1 for _i in range(n+1)]
dp[0] = 0
f = 0
from collections import deque
q = deque([0])
c = 0
for i in range(1, n+1):
    if s[i]=="0":
        c = 0
        while i-f > m:
            f = q.popleft()
        dp[i] = f
        q.append(i)
    elif c < m-1:
        c += 1
    else:
        break

if dp[n] >= 0:
    r = []
    p = n
    while p > 0:
        nex = dp[p]
        r.append(p-nex)
        p = nex
    print(*r[::-1])
else:
    print(-1)

Solution (Python):
n, m = map(int, input().split())
s = input()
dp = [-1 for _i in range(n+1)]
dp[0] = 0
f = 0
from collections import deque
q = deque([0])
c = 0
for i in range(1, n+1):
    if s[i]=="0":
        c = 0
        while i-f > m:
            f = q.popleft()
        dp[i] = f
        q.append(i)
    else:
        c += 1
        if c >= m:
            break

if dp[n] >= 0:
    r = []
    p = n
    while p > 0:
        nex = dp[p]
        r.append(p-nex)
        p = nex
    print(*r[::-1])
else:
    print(-1)

Solution (Python):
n, m = map(int, input().split())
s = input()
out_s='1'*(m)
if out_s in s:
    print(-1)
    exit()
s = s[::-1]
if s[0] == "1":
    print(-1)
    exit()
pre = [-1] * (n + 1)
stack = [0]
while stack:
    now = stack.pop()
    if now == n:
        break
    for i in range(1, m + 1):
        tsugi = now + i
        if tsugi > n:
            continue
        if s[tsugi] == "1":
            continue
        pre[tsugi] = now
        stack.append(tsugi)
else:
    print(-1)
    exit()
ato = n
mae = pre[n]
ans = []
while mae >= 0:
    ans.append(ato - mae)
    ato = mae
    mae = pre[ato]
print(*ans, sep=" ")

Solution (Python):
n, m = map(int, input().split())
s = input()
out_s='1'*(m)
if out_s in s:
    print(-1)
    exit()
s = s[::-1]
if s[0] == "1":
    print(-1)
    exit()
pre = [-1] * (n + 1)
stack = [0]
while stack:
    now = stack.pop()
    if now == n:
        break
    for i in range(1, m + 1):
        tsugi = now + i
        if tsugi > n:
            continue
        if s[tsugi] == "1":
            continue
        pre[tsugi] = now
        stack.append(tsugi)
else:
    print(-1)
    exit()
ato = n
mae = pre[n]
ans = []
while mae >= 0:
    ans.append(ato - mae)
    ato = mae
    mae = pre[ato]
print(*ans, sep=" ")

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

import math
import bisect

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

if "1"*M in S:
  print(-1)
  exit()  

S = [int(S[i]) for i in range(N+1)]

L = [(1<<i) -1 for i in range(1,M+1)]

max_n = [0]
mask = (1<<M) -1
b = 0
for i in range(N):
  b = ((b<<1) + (1- S[i])) & mask
  max_n.append(bisect.bisect_left(L,b)+1)

now = N
deme = []
while now != 0:
  x = max_n[now]
  now -= x
  deme.append(x)
print(*deme[::-1])

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

cnt=0
for i in range(len(s)):
    if s[i]=="1":
        cnt+=1
        if cnt>=m:
            print(-1)
            exit()
    else:
        cnt=0

cnt=0
from collections import defaultdict
d = defaultdict(int)
d[cnt]=n
for i in reversed(range(len(s))):
    if d[cnt] - i > m:
        cnt+=1
    if s[i]=="0":
        d[cnt+1]=i
d[cnt+1]=0

ans=[]
for i in reversed(range(len(d)-1)):
    ans.append(d[i] - d[i+1])
print(*ans,sep=" ")

Solution (Python):
import sys
N,M=map(int,input().split())
S=input()
lst=[]
koma=N
rs=0
ME=0
pn=0
while koma>0 and pn==0:
 rs+=1
 if int(S[koma-rs])==0:
  ME=rs
 if koma-rs==0 or rs==M:
  lst.append(ME)
  if ME==0:
   pn+=1
  koma-=ME
  rs=rs-ME
  ME=0
if pn>0:
 print(-1)
else:
 lst.reverse()
 print(*lst)

Solution (Python):
from collections import deque
N,M=map(int,input().split())
S=list(input()) 
flag=1
done=0
piv=N
ans=deque()
while flag==1:
    done=0
    for i in range(max(0,piv-M),piv):
        if S[i]=="0":
            ans.appendleft(piv-i)
            piv=i
            done=1
            break
    if piv==0:
        break
    if done==0:
        flag=0
        break
    

if flag==1:
    print(*ans)
else:
    print("-1")

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

S.reverse()



a = 0  
A = []  

while a < N:
    if N-a <= M:
        A.append(N-a)
        a = N
    else:
        for i in range(M,0,-1):
            if S[a+i] == 0:
                A.append(i)
                a += i
                break
        else:
            print(-1)
            exit()

A.reverse()
print(*A)

Solution (Python):



N,M = map(int, input().split())
S = input()
cnt = 0
for s in S:
    if s == "0":
        cnt = 0
    else:
        cnt += 1
        if cnt >= M:
            print(-1)
            exit()


"""
辞書順最小
・より少ない回数でゴール
・同じ回数なら、低い数字ほど左にくる

N歩先がゴール　→　出目の合計がNになったらOK
iマス目を踏むとゲームオーバー　→　途中で出目の合計がiになるとアウト

ただ、辞書順が厄介
N=4, 00000があったとして、M=3の場合、3->1より1->3の方が辞書順で若い。なので、スタート地点から貪欲に進めるだけ進む、は条件を満たさない。
→　ゴールからスタートに帰る。移動方法は貪欲にする。
"""

ans = []
rS = S[::-1]
l = 0
r = 1
while l < N:
    r = l + 1
    stoppable = l
    while r - l <= M and r <= N:
        if rS[r] == "0":
            stoppable = r
        r += 1
    
    ans.append(stoppable - l)

    l = stoppable

print(*ans[::-1])

Solution (Python):
N, M = map(int, input().split())
S = list(map(int, reversed(input())))
now = 0
ans = []
while now + M < N:
    last = now
    now += M
    while S[now]:
        now -= 1
    if last == now:
        print(-1)
        break
    ans.append(now - last)
else:
    print(*reversed(ans + [N - now]))

Solution (Python):
n,m = map(int, input().split())
s = input()
s = s[::-1]
ans = list()
goal = False
now = 0
while not goal:
    for adv in reversed(range(1,m+1)):
        if now + adv >= n:
            ans.append(n-now)
            goal = True
            break
        elif s[now+adv] == '0':
            ans.append(adv)
            now += adv
            break
    else:
        print(-1)
        break

if goal:
    print(*ans[::-1])

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

Solution (Python):



from collections import deque
import sys

N, M = map(int, input().split())
S = list(input())[::-1]

d = deque()
res = []
prev_idx = 0

while True:
    found = False
    idx = prev_idx
    for m in range(M):
        idx += 1
        if S[idx] == '0':
            
            d.append(m+1)
            found = True
            prev_idx = idx
        if idx == N:
            res.append(str(d.pop()))
            print(' '.join(res[::-1]))
            sys.exit()
    if not found:
        print(-1)
        sys.exit()
    res.append(str(d.pop()))

Solution (Python):
import sys
N, M = map(int,input().split())
S = input()
S = S[::-1]
i = 0
ans = []
while i < N:
    flag = 0
    for j in range(M,0,-1):
        if i + j <= N and S[i + j] == '0':
            i += j
            flag = 1
            ans.append(j)
            break
    if flag:
        continue
    print(-1)
    sys.exit()
ans.reverse()
print(*ans)

Solution (Python):


safe=[]
n,m=map(int,input().split())
field=list(input())
for i in range(n+1):
    if field[i]=="0":
        safe.append(i)
start=n

import bisect

deque=[]
flag=True
while start>0:
    if start>=m:
        index=bisect.bisect_left(safe,start-m)
        if safe[index]!=start:
            deque.append(start-safe[index])
            start=safe[index]           

        elif safe[index]==start:
            flag=False
            start=0              
    else:
        deque.append(start)
        start=0
if flag:
    deque=deque[::-1]
    print(*deque)
else:
    print(-1)

Solution (Python):


import sys






















def main():
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n, m = mi()
    s = input()    
    minimum_turn = 1
    ans = []
    prev = n
    current = prev - m
    while current > 0:
        for i in range(current, prev):
            if s[i] == '0':
                ans.append(m - (i - current))
                prev = i
                current = i - m
                minimum_turn += 1    
                break
        else:
            print(-1)
            exit()
    
    
    ans.append(n - sum(ans))
    ans.reverse()
    print(*ans)


if __name__ == "__main__":
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    
    

    n,m = map(int, input().split())
    s = input().rstrip()
    s = s[::-1]
    
    safe = []
    for i in range(n+1):
        if s[i] == '0':
            safe.append(i)
    res = []

    pos = 0
    while pos < n:
        pre = pos
        pos += m
        if pos >= n:
            res.append(str(n-pre))
            break
        idx = bisect_left(safe, pos)
        if safe[idx] > pos:
            pos = safe[idx-1]
        if pre == pos:
            print(-1)
            exit()
        res.append(str(pos-pre))
    print(*res[::-1])

if __name__ == '__main__':
    main()

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

s = input()

ans = []
p = n

flag = 1
while flag:
    for j in range(m,0,-1):
        if p-j<=0:
            ans.append(p)
            flag = 0
            break
        elif s[p-j]=='0':
            ans.append(j)
            p-=j
            break
        elif j == 1:
            ans.append(-1)
            flag = 0
            break

print(' '.join(map(str,reversed(ans))) if ans[-1]!=-1 else -1)

Solution (Python):

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,M=MI()
    S=list(input())
    S2=S[::-1]
    
    now=0
    ans=[]
    while now!=N:
        nxt=now+M
        if nxt>N:
            nxt=N
        while S2[nxt]=="1":
            nxt-=1
        if now==nxt:
            ans=[-1]
            break
        ans.append(nxt-now)
        now=nxt
        
    print(' '.join(map(str, ans[::-1])))
    
main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from collections import deque

n, m = map(int, readline().split())
s = readline().rstrip().decode()[::-1]
index = 0
ans = deque([])
for i in range(n):
    for j in range(m, 0, -1):
        if index + j >= n:
            ans.appendleft(n - index)
            print(*ans)
            exit()
        if s[index + j] == '0':
            ans.appendleft(j)
            index += j
            break
    else:
        print(-1)
        exit()

Solution (Python):
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,m = na()
s = list(ns())
s = s[::-1] 

ans = []
i = 0
while True:
    j = i+m if i+m < n else n
    for k in reversed(range(i+1,j+1)):
        if s[k] == '0':
            ans.append(k-i)
            i = k
            break
    else:
        print(-1)
        exit()
    if i == n:
        break

print(*ans[::-1],sep=' ')

Solution (Python):
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]
def init_dp1(init, N): return [init for _ in range(N)]
def init_dp2(init, N, M): return [[init for _ in range(M)] for _ in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    N, M = read_values()
    S = input().strip()[::-1]
    P = []
    t = 0
    tmp = 1
    for s in S[1:]:
        if s == "0":
            t = tmp
        
        tmp += 1
        if tmp > M:
            if t == 0:
                print(-1)
                return

            P.append(str(t))
            tmp -= t 
            t = 0
    
    if t != 0:
        P.append(str(t))
    print(" ".join(P[::-1]))


if __name__ == "__main__":
    main()

Solution (Python):
from bisect import *
n,m = map(int,input().split())
S = input()
ok = []
for i,s in enumerate(S[::-1]):
    if s == '0':
        ok.append(i)

now = 0
ans = []
while now != n:
    nxt = ok[bisect_right(ok, now + m) - 1]
    if nxt == now:
        ans = [str(-1)]
        break
    else:
        ans.append(str(nxt - now))
        now = nxt
print(' '.join(ans[::-1]))

Solution (Python):
import bisect

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

ok = True
cnt = 0
for c in S:
    if c == "1":
        cnt += 1
        if cnt == M:
            ok = False
            break
    else:
        cnt = 0


ngo_pos = [0 for _ in range(N+1)]
most_neighbor_zero_pos = N
for i in range(N, -1, -1):
    if S[i] == "0":
        ngo_pos[i] = i
        most_neighbor_zero_pos = i
    else:
        ngo_pos[i] = most_neighbor_zero_pos

if not ok:
    print(-1)
else:
    ans = []
    pos = N
    while pos > 0:
        npos = ngo_pos[max(0, pos-M)]
        ans.append(pos-npos)
        pos = npos
    print(" ".join(map(str, ans[::-1])))

Solution (Python):
import sys

N, M = map(int, input().split())
S = input()
tmp = 0
for i in range(N+1):
	if S[i] == '1':
		tmp += 1
		if tmp == M:
			print(-1)
			sys.exit()
	else:
		tmp = 0

ans = []

i = N
while i > M:
	ind = S[i-M:i].find('0')
	ans.append(M-ind)
	i -= M - ind

ans.append(i)

print(*ans[::-1])

Solution (Python):
import sys



def main():
	n, m = map(int, input().split())
	s=input()
	s=s[::-1]
	
	
	pos=0
	ret=[]
	while pos < len(s)-1:
		for mi in range(m,0,-1):
			if pos+mi >= len(s):
				pass
			elif s[pos+mi]=='0':
				pos += mi
				ret.append(mi)
				
				break
			else:
				pass
		else:
			return -1
	
	r=ret[::-1]
	print(*r)
	
'''
def main2():
	n, m = map(int, input().split())
	s = input()
	
	tt=[-1]*len(s)
	t_parent=[-1]*len(s)
	rs=s[::-1]
	open_list=[0]
	max_dist = 0
　	while True
		st, parent, count = open_list.pop()
		for i in range(m, 0, -1):
			aa = st + i
			if aa > n+1:
				pass
			
			
			if rs[aa] == 1:
				continue
			
			
			if tt[aa] > 0:
				break
				
			tt[aa] = count+1
			t_parent[aa] = st
			open_list.append(aa, st, count+1)
			
	print(1)
'''
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

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

if "1" * m in s:
    print(-1)
    exit()

pos = n
ans = []
while pos > 0:
    prev = max(pos - m, 0)
    while s[prev] == "1":
        prev += 1

    ans.append(pos - prev)

    pos = prev

ans = ans[::-1]
print(*ans)

Solution (Python):
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
t=list(input().rstrip())
s=[]
for i in range(n+1):
    s.append(int(t[n-i]))
ans=[]
now=0
while now<n:
    for i in range(m,0,-1):
        if now+i<=n:
            if s[now+i]==0:
                ans.append(i)
                now=now+i
                break
    else:
        print(-1)
        sys.exit()
ans.reverse()
for i in ans:
    print(i,end='')
    print(' ',end='')