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):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7





def segfunc(x, y):
    return min(x, y)

ide_ele = float('inf')

class SegTree:
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res



N, M = getNM()
S = input()
trap = set()
for i in range(len(S)):
    if S[i] == '1':
        trap.add(i)










dp = [float('inf')] * (N + 1)
dp[0] = 0
seg = SegTree([float('inf')] * (N + 1), segfunc, ide_ele)
seg.update(0, 0)

for i in range(1, N + 1):
    if i in trap:
        continue
    min_t = seg.query(max(0, i - M), i)
    seg.update(i, min_t + 1)
    dp[i] = min_t + 1

if dp[-1] == float('inf'):
    print(-1)
    exit()

dis = [[] for i in range(dp[-1] + 1)]
for i in range(len(dp)):
    if dp[i] == float('inf'):
        continue
    dis[dp[i]].append(i)

now = dp[-1]
now_index = N
ans = []
for i in range(now, 0, -1):
    index = bisect_left(dis[i - 1], now_index - M)
    ans.append(now_index - dis[i - 1][index])
    now_index = dis[i - 1][index]

for i in ans[::-1]:
    print(i)

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, m = map(int, readline().split())
    s = input()
    t = [0] * (n + 1)

    cur = n
    for i in range(n, -1, -1):
        if s[i] == "0":
            cur = i
            t[i] = cur
        else:
            t[i] = cur

    res = []

    i = n
    while i > 0:
        nx = max(0, i - m)
        if t[nx] == i:
            return print(-1)
        else:
            res.append(i - t[nx])
            i = t[nx]

    print(*res[::-1])


if __name__ == '__main__':
    main()

Solution (Python):

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

i = N
ans = []
while i > 0:
    for j in reversed(range(1, M + 1)):
        if i - j >= 0 and S[i - j] == "0":
            ans.append(j)
            i -= j
            break
    else:
        ans = []
        break

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

Solution (Python):
n, m = (int(x) for x in input().split())
s = input()
t = list(reversed(s))

ANS = []
i = 0
while i < n:
    for j in reversed(range(1, m+1)):
        if i+j > n:
            continue
        else:
            if t[i+j] == "1":
                continue
            else:
                ANS.append(j)
                i += j
                break
    else:
        print(-1)
        exit()

print(*reversed(ANS))

Solution (Python):
n,m=list(map(int,input().split()))
s=input()
a=[0]*(n+1)
a[0]=1

for i in range(1,n+1):
    if s[i]=='1':
        continue
    for j in range(max(0,i-m),i):
        if s[j]=='1':
            continue
        if a[j]>0:
            break
    
    a[i]=i-j

ans=''

cur=n
while cur>0:
    d=a[cur]
    cur-=d
    if d==0:
        print(-1)
        exit(0)

    ans=str(d)+' '+ans

print(ans[:-1])

Solution (Python):
n,m=map(int,input().split())
s,l=input(),[]
while n>0:
 for i in range(m,0,-1):
  if i<=n and s[n-i]=="0":l.append(i);n-=i;break
 else:exit(print(-1))
print(*l[::-1])

Solution (Python):
def main():
    N, M = map(int, input().split())
    *G, = map(int, input())

    ans = []
    cur = N
    ecur = cur - 1
    while cur > 0:
        ncur = cur
        while (cur - ecur) <= M and ecur >= 0:
            if G[ecur] == 0:
                ncur = ecur
            ecur -= 1

        if ncur == cur:
            print(-1)
            return

        ans.append(cur - ncur)
        cur = ncur

    ans.reverse()

    print(*ans)


if __name__ == '__main__':
    main()

Solution (Python):
N,M=map(int,input().split())
S=input()
S=S[::-1]
now = 0
ok=1
history = []
while True:
  for i in range(min(M, N-now),0,-1):
    if S[now+i] == '0':
      now += i
      history.append(str(i))
      break
    if i==1:
      print(-1)
      ok=0
      break
  if ok==0:break
  if now == N:break

if ok==1:print(' '.join(history[::-1]))

Solution (Python):
from collections import deque
from bisect import bisect_right
INFTY = 10**6
N,M = map(int,input().split())
S = input().strip()
dp = [INFTY for _ in range(N+1)]
dp[N]=0
A = deque([])
B = {}
pre = N
flag = 0
for i in range(N-1,-1,-1):
    if S[i]=="0":
        ind = bisect_right(A,i+M)
        if ind>0:
            dp[i] = dp[A[ind-1]]+1
            B[i] = A[ind-1]
            if dp[i]>dp[pre]:
                A.appendleft(pre)
        else:
            if pre<=i+M:
                dp[i]=dp[pre]+1
                B[i] = pre
                A.appendleft(pre)
            else:
                flag = 1
                break
        pre = i
if flag==0:
    P = []
    k = 0
    while k<N:
        P.append(B[k]-k)
        k = B[k]
    print(*P)
else:
    print(-1)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M = mapint()
S = list(input())

def solve():
    now = N
    choice = []
    while 1:
        if now==0:
            return choice[::-1]
        for m in range(M, 0, -1):
            nx = now-m
            if nx<0: continue
            if S[nx]=='1': continue
            now = nx
            choice.append(m)
            break
        else:
            return [-1]

print(*solve())

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

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

print(*ans[::-1])

Solution (Python):
import sys
n,m=map(int,input().split())
s=input()
ans=[]
current=n
while current>0:
  for i in range(m):
    if current-(m-i)<0:
      continue
    if s[current-(m-i)]=='0':
      current-=(m-i)
      ans.append(str(m-i))
      break
    if i==m-1:
      print(-1)
      sys.exit()
ans.reverse()
print(' '.join(ans))

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

S.reverse()
ans = []
i = 0
while i < N:
    num = 0
    for j in range(min(N, i+M), i, -1):
        if S[j] == "0":
            num = j-i
            i = j
            break
    if num == 0:
        ans = -1
        break
    ans.append(num)

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

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

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = list(map(int, input().split()))
s = input()
c = n
ans = []
while c>0:
    val = None
    for i in range(1,m+1):
        if c-i>=0 and s[c-i]=="0":
            val = i
    if val is None:
        ans = -1
        break
    c = c-val
    ans.append(val)
if ans==-1:
    print(ans)
else:
    write(" ".join(map(str, ans[::-1])))

Solution (Python):

N, M = map(int, input().split())
s = input()
ans = []
cur = N
while cur != 0:
    for step in range(M, 0, -1):
        if cur - step < 0:
            continue
        if s[cur-step] == '1':
            continue
        ans.append(step)
        cur -= step
        break
    else:
        print(-1)
        exit()
print(*ans[::-1])

Solution (Python):
import heapq


def main():
    N, M = list(map(int, input().split(' ')))
    S = input()
    
    T = S[::-1]  
    dp = [-1] * (N + 1)
    que = [0] * M
    for i, t in enumerate(T):
        if i == 0:
            dp[0] = 0
            continue
        if len(que) == 0:
            print(-1)
            return
        index = heapq.heappop(que)
        if t == '1':
            continue
        dp[i] = 1 + dp[index]
        while len(que) < M:
            heapq.heappush(que, i)
    dp.reverse()
    
    path = list()
    target = dp[0] - 1
    cnt = 0
    for i in range(N + 1):
        if dp[i] != target:
            cnt += 1
        else:
            path.append(cnt)
            cnt = 1
            target -= 1
    print(' '.join(map(str, path)))


if __name__ == '__main__':
    main()

Solution (Python):

import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import copy
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


def solve():
    N, M = Scanner.map_int()
    S = Scanner.string()
    pos = N
    ans = []
    while pos > 0:
        for i in range(max(pos - M, 0), pos):
            if S[i] == '0':
                ans.append(pos - i)
                pos = i
                break
        else:
            print(-1)
            return
    print(*ans[::-1])


def main():
    
    
    solve()


if __name__ == "__main__":
    main()

Solution (Python):
n, m = map(int, input().split())
s = input()
s = ''.join(reversed(s))
ans = []
index = 0
while index < n:
    next_index = -1
    for j in range(min(index + m, n), index, -1):
        if s[j] == '0':
            next_index = j
            break
    if next_index == -1:
        ans = [-1]
        break
    ans.append(next_index - index)
    index = next_index 
print(' '.join(list(map(str, list(reversed(ans))))))

Solution (Python):
N,M=map(int, input().split())
S=list(input())
T=S[::-1]
D=[0]*N
if N<=M:
  print(N)
  exit()
renzoku,ma=0,0
for i in range(1,N+1):
  if S[i]=='1':
    renzoku+=1
  else:
    ma=max(ma,renzoku)
    renzoku=0
if ma>=M:
  print(-1)
  exit()
r=0
for i in range(1,M+1):
  if T[i]!='1':
    r=i
ans=[r]

while r+M<N:
  for i in range(M,0,-1):
    if T[r+i]=='0':
      ans.append(i)
      r+=i
      break
  
ans.append(N-r)
print(*ans[::-1])

Solution (Python):
N,M=map(int, input().split())
S=list(input())
T=S[::-1]
D=[0]*N
if N<=M:
  print(N)
  exit()
r=0
renzoku,ma=0,0
for i in range(1,N+1):
  if S[i]=='1':
    renzoku+=1
  else:
    ma=max(ma,renzoku)
    renzoku=0
if ma>=M:
  print(-1)
  exit()

for i in range(1,M+1):
  if T[i]!='1':
    D[i]=1
    r=i
  else:
    D[i]=100000
ans=[r]

while r+M<N:
  for i in range(M,0,-1):
    if T[r+i]=='0':
      ans.append(i)
      r+=i
      break
  
ans.append(N-r)
print(*ans[::-1])

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

steps = []
c = N
flg = True
while flg:
    if c <= M:
        steps.append(c)
        break
    
    for i in reversed(range(1, M + 1)):
        if S[c - i] == "0":
            steps.append(i)
            c -= i
            break
        if i == 1:
            steps = [-1]
            flg = False
            
print(*steps[::-1])

Solution (Python):
n,m = map(int,input().split())
s = input()
s = s[::-1]

tmp = 0
sum1 = 0
ans = []

while tmp < n:
    for i in range(m, 0, -1):
        flag = False
        if tmp + i <= n:
            if s[tmp+i] == '0':
                tmp += i
                flag = True
                sum1 += 1
                ans.append(i)
                break
    if not flag:
        print(-1)
        exit()

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

Solution (Python):
n, m = map(int, input().split())
s = input()
s = s[::-1]
loc = 0
anslist=[]
while True:
  if loc >= n-m:
    anslist.append(n-loc)
    break
    quit()
  next = m
  while s[loc+next]=="1":
    next-=1
    if next == 0:
      print(-1)
      quit()
  anslist.append(next)
  loc+=next
ans=anslist[::-1]
ans = list(map(str, ans))
print(" ".join(ans))

Solution (Python):
import sys

import math
import collections

import bisect
import itertools
import fractions

import copy

import decimal

import queue



sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))





def main():
    n, m = ns()
    s = list(input())

    ans = []

    idx = n
    while idx != 0:
        exitFlg = True
        for i in range(min(idx, m), 0, -1):
            if s[idx - i] == "0":
                idx -= i
                ans.append(i)
                exitFlg=False
                break

        if exitFlg:
            print(-1)
            exit(0)

    ans.reverse()
    print(*ans, sep=" ")


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M = map(int, readline().split())
    S = readline().strip()

    S = S[::-1]
    idx = 0
    ans = []
    while idx < N:
        step = 0
        for i in range(min(M, N - idx), 0, -1):
            if S[idx + i] == '0':
                step = i
                break
        if step == 0:
            print(-1)
            return
        ans.append(step)
        idx += step

    print(*reversed(ans))
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M = map(int, readline().split())
    S = readline().strip()

    S = S[::-1]
    idx = 0
    ans = []
    while idx < N:
        step = 0
        for i in range(1, M + 1):
            if S[idx + i] == '0':
                step = i
            if idx + i == N:
                break
        if step == 0:
            print(-1)
            return
        ans.append(step)
        idx += step

    print(*reversed(ans))
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
import math
import bisect
from collections import deque
def input():
    return sys.stdin.readline()[:-1]
    
n,m = map(int,input().split())
s = input()
lis = []
now = len(s)-1
ju = 0
ju2 = 0
while now>0:
    ju = 0
    if ju2==1:
        break
    for i in range(m,0,-1):
        if now-i<0:
            continue
        if now-i ==0:
            lis.append(i)
            ju = 1
            now = 0
            break
        if s[now-i]=="0":
            now = now-i
            lis.append(i)
            ju = 1
            break
        if i==1 and ju==0:
            ju2 = 1
            break
if ju2==0:
    lis.reverse()
    print(*lis)
else:
    print(-1)

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

  c,l=N,[]
  while c>0:
    for i in range(M,0,-1):
      if i<=c and S[c-i]=='0':
        l+=[i]
        c-=i
        break
    else:
      l=[-1]
      break
  print(*l[::-1])

main()

Solution (Python):
n, m = map(int, input().split())
n += 1
s = list(input())
dp = [0] * n
for i in range(1, n):
    if i - m < 0 and s[n - i - 1] == "0":
        dp[i] = 1
    elif s[n - i - 1] == "1":
        dp[i] = -1
    else:
        for j in range(i - m, i):
            if not dp[j] == -1:
                dp[i] = dp[j] + 1
                break
t = [0] * n
j = 0
x = dp[n - 1] + 1
for i in range(n - 1, -1, -1):
    if dp[i] == x - 1:
        t[j] = i
        j += 1
        x -= 1
    elif dp[i] == 0:
        print(-1)
        exit()
ans = [t[i] - t[i + 1] for i in range(j - 1)]
print(*ans)

Solution (Python):

import sys
sys.setrecursionlimit(10**6)

buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo


@mt
def slv(N, M, S):

    from functools import lru_cache
    @lru_cache(maxsize=None)
    def dfs(x):
        if x == 0:
            return []

        for i in range(M, 0, -1):
            if 0 <= x-i and S[x-i] == '0':
                r = dfs(x-i)
                if r is not None:
                    r.append(i)
                    return r
        return None
    ans = dfs(N)
    if ans is None:
        ans = [-1]
    return ans




def main():
    N, M = read_int_n()
    S = read_str()
    print(*slv(N, M, S))


if __name__ == '__main__':
    main()

Solution (Python):
import sys

input = sys.stdin.readline


def main():
    N, M = [int(x) for x in input().split()]
    S = input().strip()

    if S.count("1" * M) > 0:
        print(-1)
        return

    ans = []
    r = N
    while r > 0:
        li = N - 1
        for diff in range(1, M + 1):
            if r - diff < 0:
                break
            if S[r - diff] == "0":
                li = r - diff
        ans.append(r - li)
        r = li
        if r == 0:
            break

    ans.reverse()
    print(*ans)



if __name__ == '__main__':
    main()

Solution (Python):






n,m=map(int,input().split())
s=input()
s=s[::-1]

ans=[]
i=0
while i < n:
    best=min(i+m,n)
    flag=0
    while best>i:

        if s[best]=="0":
            ans.append(str(best-i))
            i=best
            flag=1
        else:
            best-=1


    if flag==0:
        print(-1)
        exit()

print(" ".join(ans[::-1]))

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

ans = []

now_pos = N

while now_pos > 0:
    next_pos = max(0, now_pos - M)
    for i in range(M):
        if S[next_pos + i] == "0":
            ans.append(now_pos - (next_pos + i))
            now_pos = next_pos + i
            break
    else:
        print(-1)
        exit()

print(" ".join(map(str, ans[::-1])))

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

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

print(*reversed(ans))

Solution (Python):
import sys
N,M=map(int,input().split())
slist=list(map(int,input()))

seq=0
for s in slist:
  if s==0:
    seq=0
  else:
    seq+=1
    if seq==M:
      print(-1)
      sys.exit(0)

class SegTree:
  
  def __init__(self, init_val, segfunc, ide_ele):
    
    
    
    
    
    
    n = len(init_val)
    self.segfunc = segfunc
    self.ide_ele = ide_ele
    self.num = 1 << (n - 1).bit_length()
    self.tree = [ide_ele] * 2 * self.num
    
    for i in range(n):
      self.tree[self.num + i] = init_val[i]
    
    for i in range(self.num - 1, 0, -1):
      self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

  
  def update(self, k, x):
    
    
    
    k += self.num
    self.tree[k] = x
    while k > 1:
      self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
      k >>= 1

  
  def query(self, l, r):
    
    
    
    res = self.ide_ele
    l += self.num
    r += self.num
    while l < r:
      if l & 1:
        res = self.segfunc(res, self.tree[l])
        l += 1
      if r & 1:
        res = self.segfunc(res, self.tree[r - 1])
      l >>= 1
      r >>= 1
    return res


def segfunc(x,y):
  return min(x,y) 

ide_ele=float("inf") 

seg=SegTree([float("inf")]*(N+1), segfunc, ide_ele)

dist_list=[float("inf")]*(N+1)
seg.update(N,0)
dist_list[N]=0
for i in reversed(range(N)):
  if slist[i]==0:
    left=i+1
    right=min(i+M,N)
    dist=seg.query(left,right+1)+1
    seg.update(i,dist)
    dist_list[i]=dist

answer_list=[]
i=0
while i<N:
  for j in range(1,M+1):
    if dist_list[i]>dist_list[i+j]:
      answer_list.append(j)
      i+=j
      break
    
print(*answer_list)

Solution (Python):
import sys
N,M=map(int,input().split())
slist=list(map(int,input()))

seq=0
for s in slist:
  if s==0:
    seq=0
  else:
    seq+=1
    if seq==M:
      print(-1)
      sys.exit(0)


def segfunc(x,y):
  return min(x,y)


ide_ele=float("inf")

class SegTree:
  """
  init(init_val, ide_ele): 配列init_valで初期化 O(N)
  update(k, x): k番目の値をxに更新 O(logN)
  query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
  """
  def __init__(self, init_val, segfunc, ide_ele):
    """
    init_val: 配列の初期値
    segfunc: 区間にしたい操作
    ide_ele: 単位元
    n: 要素数
    num: n以上の最小の2のべき乗
    tree: セグメント木(1-index)
    """
    n = len(init_val)
    self.segfunc = segfunc
    self.ide_ele = ide_ele
    self.num = 1 << (n - 1).bit_length()
    self.tree = [ide_ele] * 2 * self.num
    
    for i in range(n):
      self.tree[self.num + i] = init_val[i]
    
    for i in range(self.num - 1, 0, -1):
      self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

  def update(self, k, x):
    """
    k番目の値をxに更新
    k: index(0-index)
    x: update value
    """
    k += self.num
    self.tree[k] = x
    while k > 1:
      self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
      k >>= 1

  def query(self, l, r):
    """
    [l, r)のsegfuncしたものを得る
    l: index(0-index)
    r: index(0-index)
    """
    res = self.ide_ele

    l += self.num
    r += self.num
    while l < r:
      if l & 1:
        res = self.segfunc(res, self.tree[l])
        l += 1
      if r & 1:
        res = self.segfunc(res, self.tree[r - 1])
      l >>= 1
      r >>= 1
    return res
  
seg=SegTree([float("inf")]*(N+1), segfunc, ide_ele)
seg.update(N,0)

for i in reversed(range(N)):
  if slist[i]==0:
    left=i+1
    right=min(i+M,N)
    seg.update(i,seg.query(left,right+1)+1)

dist_list=[]
for i in range(N+1):
  dist_list.append(seg.query(i,i+1))


answer_list=[]
i=0
while i<N:
  for j in range(1,M+1):
    if dist_list[i]>dist_list[i+j]:
      answer_list.append(j)
      i+=j
      break
    
print(*answer_list)

Solution (Python):
n, m = map(int, input().split())
sugoroku = input()[::-1]

cnt = 0
pos = 0
tmp = 0
lst = []
while pos != n:
    pos += 1
    cnt += 1
    if cnt == m:
        if sugoroku[pos] == "0":
            lst.append(cnt)
            cnt = 0
        else:
            if tmp == 0:
                print(-1)
                exit()
            lst.append(tmp)
            cnt -= tmp
            tmp = 0
    else:
        if sugoroku[pos] == "0":
            tmp = cnt
if cnt != 0:
    lst.append(cnt)
for num in lst[::-1]:
    print(num, end = " ")

Solution (Python):
from bisect import *
n, m = map(int, input().split())
s = input()

masu = []
for i in range(n+1):
    if s[i] == "0":
        masu.append(i)

now = n
ans = [n]

while now > 0:
    next = masu[bisect_left(masu, now-m)]
    if now != next:
        ans.append(next)
        now = next
    else:
        ans = -1
        break

if ans == -1:
    print(-1)

else:
    ans.reverse()
    for i in range(len(ans)-1):
        print(ans[i+1]-ans[i])

Solution (Python):
n,m = map(int,input().split())
s = input()[::-1]


count = 1
inf = 10**10


length = [inf]*(n+1)
length[0] = 0
now = 0
flag = True

while flag:
    ok = 0
    for i in range(1,m+1):
        if s[now+i] == "1":
            continue
        length[now+i] = count
        ok = now+i
        if now+i == n:
            flag = False
            break
    if ok == 0:
        print(-1)
        exit()
    now = ok
    count += 1

count -= 2


li = []
length = length[::-1]
point = 0

for i,j in enumerate(length):
    if j == count:
        count -= 1
        li.append(point)
        point = 0
    point += 1

print(*li)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = map(int, input().split())
s = input()
c = n
ans = []
while True:
    p = None
    for i in range(1,m+1):
        if c-i>=0 and s[c-i]=="0":
            p = i
    if p is None:
        ans = -1
        break
    c -= p
    ans.append(p)
    if c==0:
        break
if ans==-1:
    print(ans)
else:
    write(" ".join(map(str, ans[::-1])))

Solution (Python):
n,m=map(int,input().split())
s=input()[::-1]
ans=[]
now=0
while n>m-1:
  x=s[now+1:now+m+1][::-1]
  memo=x.find('0')
  if memo<0:
    print(-1)
    quit()
  n-=(m-memo)
  now+=(m-memo)
  ans.append(str(m-memo))
if n>0:
  ans.append(str(n))
print(' '.join(ans[::-1]))

Solution (Python):
import math

import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,m = map(int,ipt().split())
    s = input()[::-1]
    ni = 0
    me = []
    while ni < n:
        for i in range(m):
            if ni+m-i <= n and s[ni+m-i] == "0":
                ni = ni+m-i
                me.append(str(m-i))
                break
            if i == m-1:
                print(-1)
                exit()
    print(" ".join(me[::-1]))
    return

if __name__ == '__main__':
    main()

Solution (Python):
N,M=map(int, input().split())
S=input()
now=S[N-1]
dp=[float("INF")]*(N+1)
dp[N]=0
nowmin=0
right=N
for left in range(N-1,-1,-1):
    while right-left>M or S[right]=="1":
        right-=1
        nowmin=dp[right]
    if right<=left:
        print(-1)
        exit()
    if S[left]=="1":
        continue
    else:
        dp[left]=1+nowmin


now=dp[0]
nowi=0
"""
if now==float("INF"):
    print(-1)
    exit()
"""
for i in range(1,N+1):
    if now>dp[i]:
        print(i-nowi, end=" ")
        now=dp[i]
        nowi=i

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

if M >= N:
    print(N)
    exit()

p = -1
for i in reversed(range(1,M+1)):
    if S[i] == "0":
        p = i
        break

if p == -1:
    print(-1)
    exit()

ps = [p]
while 1:
    tmp = -1
    for i in reversed(range(ps[-1]+1,ps[-1]+M+1)):
        try:
            if S[i] == "0" or i == N:
                ps.append(i)
                tmp = i
                break
        except:
            pass
    if tmp == -1:
        print(-1)
        exit()
    if ps[-1] == N:
        break

pp = ([ps[i+1]-ps[i] for i in range(len(ps)-1)])[::-1] + [ps[0]]
print(*pp)