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

class SegTree:
    """
    セグメント木
    1.update:  i番目の値をxに更新する
    2.query: 区間[l, r)の値を得る
    """

    def __init__(self, n, func, intv, A=[]):
        """
        :param n: 要素数(0-indexed)
        :param func: 値の操作に使う関数(min, max, add, gcdなど)
        :param intv: 要素の初期値(単位元)
        :param A: 初期化に使うリスト(オプション)
        """
        self.n = n
        self.func = func
        self.intv = intv
        
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [self.intv] * (n2 << 1)
        
        if A:
            
            for i in range(n):
                self.tree[n2+i] = A[i]
            
            for i in range(n2-1, -1, -1):
                self.tree[i] = self.func(self.tree[i*2], self.tree[i*2+1])

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.n2
        self.tree[i] = x
        while i > 0:
            i >>= 1
            self.tree[i] = self.func(self.tree[i*2], self.tree[i*2+1])

    def query(self, a, b):
        """
        [a, b)の値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        l = a + self.n2
        r = b + self.n2
        s = self.intv
        while l < r:
            if r & 1:
                r -= 1
                s = self.func(s, self.tree[r])
            if l & 1:
                s = self.func(s, self.tree[l])
                l += 1
            l >>= 1
            r >>= 1
        return s

    def get(self, i):
        """ 一点取得 """
        return self.tree[i+self.n2]

    def all(self):
        """ 全区間[0, n)の取得 """
        return self.tree[1]

N, M = MAP()
S = input()

dp = SegTree(N+1, min, INF)
dp.update(N, 0)
for i in range(N-1, -1, -1):
    
    if S[i] == '1':
        continue
    mn = dp.query(i+1, min(N+1, i+M+1))
    if mn != INF:
        dp.update(i, mn+1)


if dp.get(0) == INF:
    print(-1)
    exit()

cnt = dp.get(0)
cur = 0
prev = -1
ans = []
for i in range(1, N+1):
    if dp.get(i) == INF:
        continue
    
    if dp.get(i) != cnt:
        prev = cur
        cur = i
        ans.append(cur-prev)
        cnt = dp.get(i)
print(*ans)

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

class SegTree:
    """
    セグメント木
    1.update:  i番目の値をxに更新する
    2.query: 区間[l, r)の値を得る
    """

    def __init__(self, n, func, intv, A=[]):
        """
        :param n: 要素数(0-indexed)
        :param func: 値の操作に使う関数(min, max, add, gcdなど)
        :param intv: 要素の初期値(単位元)
        :param A: 初期化に使うリスト(オプション)
        """
        self.n = n
        self.func = func
        self.intv = intv
        
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [self.intv] * (n2 << 1)
        
        if A:
            
            for i in range(n):
                self.tree[n2+i] = A[i]
            
            for i in range(n2-1, -1, -1):
                self.tree[i] = self.func(self.tree[i*2], self.tree[i*2+1])

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.n2
        self.tree[i] = x
        while i > 0:
            i >>= 1
            self.tree[i] = self.func(self.tree[i*2], self.tree[i*2+1])

    def query(self, a, b):
        """
        [a, b)の値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        l = a + self.n2
        r = b + self.n2
        s = self.intv
        while l < r:
            if r & 1:
                r -= 1
                s = self.func(s, self.tree[r])
            if l & 1:
                s = self.func(s, self.tree[l])
                l += 1
            l >>= 1
            r >>= 1
        return s

    def get(self, i):
        """ 一点取得 """
        return self.tree[i+self.n2]

    def all(self):
        """ 全区間[0, n)の取得 """
        return self.tree[1]

N, M = MAP()
S = input()

dp = SegTree(N+1, min, INF)
dp.update(N, 0)
for i in range(N-1, -1, -1):
    
    if S[i] == '1':
        continue
    mn = dp.query(i+1, min(N+1, i+M+1))
    if mn != INF:
        dp.update(i, mn+1)


if dp.get(0) == INF:
    print(-1)
    exit()

cnt = dp.get(0)
cur = 0
prev = -1
ans = []
for i in range(1, N+1):
    if dp.get(i) == INF:
        continue
    
    if dp.get(i) != cnt:
        prev = cur
        cur = i
        ans.append(cur-prev)
        cnt = dp.get(i)
print(*ans)

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):

def main(n,m,s):

    
    i = n
    tmp = []
    while i > 0 :
        for j in range(m,-1,-1):
            if j == 0 :
                i = -1
                break

            if i-j >= 0 :
                if s[i-j] == '0':
                    i -= j
                    tmp.append(j)
                    break
    if i == 0:
        for l in reversed(tmp):
            print(l,end=' ')
    else:
        print(-1)


n,m = map(int,input().split())
s = input()
main(n,m,s)

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

if s.find('1' * m) != -1:
  print('-1')
  exit(0)

i = n
rans = []
flag = True
while flag:
  for j in range(m, 1 - 1, -1):
    if i - j == 0:
      flag = False
    if i - j >= 0 and s[i - j] == '0':
      rans.append(j)
      i = i - j
      break
  
print(' '.join(map(str,reversed(rans))))

Solution (Python):
n,m=map(int,input().split())
s=input()
res=[]
now=n
while now!=0:
    j=False
    for i in range(max(0,now-m),now):
        if s[i]=="0":
            j=True
            res.append(now-i)
            now=i
            
            break
    if not j:
        print(-1)
        exit()
for i in range(len(res)-1,-1,-1):
    print(res[i],end=" ")

Solution (Python):
import sys
from collections import deque
n,m=map(int,input().split())
s=input()
if n<=m:
    print(n)
    sys.exit()
lst=[0]*(n+1)
for i in range(1,m+1):
    if s[i]=="0":
        lst[i]=i
left=1
right=m+1
k=0
while left<n:
    if s[left]=="0":
        while right-left<=m:
            if s[right]=="0":
                lst[right]=right-left
            right+=1
            if right==n+1:
                k=n
                break
    left+=1
    if left==right or k==n:
        break
if lst[n]==0:
    print(-1)
else:
    ans=deque([])
    while k>0:
        c=lst[k]
        ans.appendleft(c)
        k-=c
    print(*ans)

Solution (Python):
n,m=map(int,input().split())
l=list(input())
l=l[::-1]
now=0
ans=[]
while now<n:
  num=min(n-now,m)
  b=True
  for i in range(num):
    num1=num-i
    if l[now+num1]!="1":
      ans.append(str(num1))
      now+=num1
      b=False
      break
  if b:
    now=n+1
if b:
  print(-1)
else:
  ans=ans[::-1]
  print(" ".join(ans))

Solution (Python):
N,M = [int(x) for x in input().split()]
S = list(input())
S1 = S[::-1]
ind = 0
ans = []
while ind!=N:
  ind1 = ind
  for i in range(M,0,-1):
    if ind+i<=N and S1[ind+i]=="0":
      ind = ind+i
      ans.append(i)
      break
  if ind1==ind:
    print(-1)
    exit()
print(*ans[::-1])

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007


n, m = LI()
s = S()
now = n
ans = []
while now:
    nxts = s[max(0, now - m): now]
    for i, bit in enumerate(nxts):
        if bit == '0':
            break
    else:
        print(-1)
        exit()
    move = (len(nxts) - i)
    now -= move
    ans += [move]



print(*ans[::-1])

Solution (Python):
def main():
    n,m=map(int,input().split())
    s=input()
    masu = n
    res = []
    while masu>m:
        tm = m
        while s[masu - tm]=="1":
            tm -= 1
            if tm == 0:
                return -1
        res.append(tm)
        masu -= tm
    res.append(masu)
    res.reverse()
    return " ".join(map(str,res))


print(main())

Solution (Python):
N,M=map(int,input().split())
S=list(input())
S=S[::-1]
ans=[]
P=0
for i in range(1,N+1):
    if P==N:
        break
    for j in range(M+1):
        if P+(M-j)<=N and S[P+(M-j)]=="0":
            ans.append(M-j)
            P+=M-j
            if M-j==0:
                print(-1)
                exit()
            break
ans=ans[::-1]
if 0 in ans:
    print(-1)
else:
    print(*ans)

Solution (Python):

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

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

    i = 0
    while i < N:
        for j in range(M, 0, -1):
            if i + j > N:
                continue
            if int(S[i+j]) == 0:
                ans_l.append(j)
                i += j
                break
            if j == 1:
                print(-1)
                exit()

    ans_l = ans_l[::-1]
    print(' '.join(map(str, ans_l)))


if __name__ == '__main__':
    solve()

Solution (Python):
import copy
n, m = map(int, input().split())
s = list(input())
s.reverse()
ans = []
cur_index = 0
while cur_index < n:
    pre = copy.deepcopy(cur_index)
    for i in range(min(m, n - cur_index), 0, -1):
        if s[cur_index + i] == '0':
            cur_index += i
            ans.append(i)
            break
    if pre == cur_index:
        print(-1)
        exit()
ans.reverse()
for i in ans:
    print("{} ".format(i), end = "")

Solution (Python):
def main():
	n, m = map(int, input().split())
	rev = input()[::-1]
	ans = []
	cur = nxt = 0
	while cur < n:
		for i in range(cur + 1, cur + m + 1):
			if i==n:
				nxt = i
				break
			if rev[i]=="0":
				nxt = i
		if cur==nxt:
			print(-1)
			exit()
		ans += [str(nxt - cur)]
		cur = nxt
	print(" ".join(ans[::-1]))


if __name__=="__main__":
	main()

Solution (Python):
n,m=map(int,input().split())
su=input()
rev=su[::-1]
if "1"*m in su:
	print(-1)
	exit()
dist_f_n=[float('inf')]*(n+1)
dist_f_n[0]=0
for i in range(1,m+1):
	if rev[i]=="0":
		dist_f_n[i]=1
		last=i
		if i==n:
			break
while last<n:
	for i in range(last+1,last+m+1):
		if rev[i]=="0":
			dist_f_n[i]=dist_f_n[last]+1
			_last=i
			if i==n:
				break
	last=_last
cur=dist_f_n[-1]
_i=0
ans=[]
for i,x in enumerate(dist_f_n[::-1]):
	if x==cur-1:
		ans.append(i-_i)
		cur-=1
		_i=i
print(" ".join(map(str,ans)))

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

ans = []
x = len(S) - 1
while x:
    for step in range(m, 0, -1):
        if x - step < 0:
            continue
            
        to = S[x-step]
        if to == '1':
            continue
        else:
            x -= step
            ans.append(str(step))
            break
    else:
        print(-1)
        exit()

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

Solution (Python):

import sys











sys.setrecursionlimit(10**8)


def inp(): 
    return int(input())
def inpm(): 
    return map(int,input().split())
def inpl(): 
    return list(map(int, input().split()))
def inpls(): 
    return list(input().split())
def inplm(n): 
    return list(int(input()) for _ in range(n))
def inpll(n): 
    return sorted([list(map(int, input().split())) for _ in range(n)])
    
def main():
    n,m=inpm()
    s=list(input())
    s.reverse()
    s=tuple(s)
    ans = []
    now = 0
    while True:
        key = 0
        for go in range(m,0,-1):
            if now+go>=n:
                x=n-now
                ans.append(str(x))
                ans.reverse()
                print(' '.join(ans))
                return
            elif s[now + go]=='0':
                key = 1
                now+=go
                ans.append(str(go))
                break
        if key == 0:
            print(-1)
            return

if __name__ == "__main__":
    main()

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

DP, prev_i = [0] + [-1] * N, 0
for i in range(N):
    s = S[-2 - i]
    prev_i = max(prev_i, i + 1 - M)
    if s == '0':
        while DP[prev_i] == -1 and prev_i < i + 1:
            prev_i += 1
        if prev_i >= i + 1:
            break
        DP[i + 1] = DP[prev_i] + 1

if DP[-1] == -1:
    print(-1)
else:
    df, ans = [0] * (DP[-1] + 1), []
    for i in range(N + 1):
        if DP[i] >= 1:
            df[DP[i]] = i
    for i in range(DP[-1]):
        ans.append(df[-1 - i] - df[-2 - i])
    print(' '.join(map(str, ans)))

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

ans = []
C = -1
lastZero = 0
lastStop = 0
flag = True
for i, v in enumerate(S):
    C += 1
    if v == '0':
        lastZero = i
    elif i - lastZero >= M:
        flag = False
        break
    if C == M:
        ans.append(lastZero - lastStop)
        lastStop = lastZero
        C = i - lastStop
    elif i == N:
        ans.append(C)

if flag:
    for i in range(len(ans)-1, -1, -1):
        print(ans[i],end='')
        if i > 0:
            print(' ',end='')
        else:
            print()
else:
    print(-1)

Solution (Python):
n, m = map(int,input().split())
s = input()
ans = []
p = n
while m < p:
    for i in range(m, 0, -1):
        if s[p - i] == "0":
            ans.append(i)
            break
        else:
            if i == 1:
                print(-1)
                exit()
            else:
                continue
    p -= i
ans.append(p)
k = len(ans)
for i in range(k):
    if i == k-1:
        print(ans[k-i-1])
    else:
        print(ans[k-i-1], end=" ")

Solution (Python):
N,M=map(int,input().split())
S=input()
cur=N
can_points=[N]
while cur>0:
  point=cur
  for i in range(min(M,cur)):
    if int(S[cur-1-i])==0:
      point=cur-1-i
  if point==cur:
    break
  else:
    cur=point
    can_points.append(point)
if cur>0:
    print(-1)
else:
    l=[]
    s=len(can_points)
    for i in range(s-1):
        l.append(str(can_points[s-2-i]-can_points[s-1-i]))
        l.append(' ')
    print(''.join(l))

Solution (Python):
n,m=map(int,input().split())
*s,=map(int,input()[::-1])
a=[]
i=0
while i<n:
  j=max(j for j in range(i,min(n,i+m)+1)if not s[j])
  if i==j:
    print(-1)
    exit()
  a+=j-i,
  i=j
print(*a[::-1])

Solution (Python):
n,m=map(int,input().split())
*s,=map(int,input()[::-1])
a=[]
i=0
while i<n:
  j=max(j for j in range(i,min(n,i+m)+1)if not s[j])
  if i==j:
    print(-1)
    exit()
  a+=j-i,
  i=j
print(*a[::-1])

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

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


def solve(x):
    if x <= m + 1:
        return [x - 1]
    for i in range(m, 0, -1):
        if s[x - 1 - i] == 0:
            cand = solve(x - i)
            if len(cand) != 0:
                cand.append(i)
                return cand

    return []


cnt1_continuous = 0
cnt = 0
for i in range(n + 1):
    if s[i] == 1:
        cnt += 1
        if i == n:
            cnt1_continuous = max(cnt1_continuous, cnt)
    else:
        cnt1_continuous = max(cnt1_continuous, cnt)
        cnt = 0

if cnt1_continuous >= m:
    print(-1)
else:
    print(*solve(len(s)))

Solution (Python):
N,M = map(int,input().split())
S = input()
S = S[::-1]
s = 0
used = [0]
while s < N:
    for i in range(M,-1,-1):
        if s+i > N:
            i = N-s
        if S[s+i]=='0':
            s += i
            used.append(s)
            break
    if i==0:
        break
if s==N:
    ans = []
    for i in range(len(used)-1):
        ans.append(used[i+1]-used[i])
    ans = ans[::-1]
    ans = ' '.join([str(c) for c in ans])
    print(ans)
else:
    print(-1)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

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


def solve(t):
    if len(t) <= m + 1:
        return [len(t) - 1]
    for i in reversed(range(1, m + 1)):
        if t[len(t) - 1 - i] == '0':
            cand = solve(t[:-i])
            if len(cand) != 0:
                cand.append(i)
                return cand

    return []


cnt1_continuous = 0
cnt = 0
for i in range(n + 1):
    if s[i] == '1':
        cnt += 1
        if i == n:
            cnt1_continuous = max(cnt1_continuous, cnt)
    else:
        cnt1_continuous = max(cnt1_continuous, cnt)
        cnt = 0

if cnt1_continuous >= m:
    print(-1)
else:
    if m == 1:
        ans = [1] * n
    else:
        ans = solve(s)
    print(*ans)

Solution (Python):

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

S_inv = S[::-1]
count = 0
ans_inv = []
flag = True
flag2 = True

while flag:
    for i in range(M):
        if len(S_inv) - count - 1 < M:
            if len(S_inv) - count - 1 != 0:
                ans_inv.append(len(S_inv) - count - 1)
            flag = False
            break
        elif S_inv[count + M - i] == "0":
            count += M - i
            ans_inv.append(M - i)
            break
    else:
        flag2 = False
        break

if flag2:
    print(*ans_inv[::-1])
else:
    print(-1)

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






def getFarthest(start):
    for i in range(min(n,start+m),start-1,-1):
        if s[i] == '0':
            return i

ans = []
start = 0
found = True
while True:
    nxt = getFarthest(start)
    if nxt == start:
        found = False
        break
    ans.append(nxt - start)
    start = nxt
    if start == n:
        break
ans = ans[::-1]
if found:
    for i in ans:
        print(i,end=" ")
    print()
else:
    print(-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):
import collections
import heapq
def main():

    N, M = map(int, input().split())
    S = input()
    h = []
    w = []
    heapq.heappush(h, [0, N])
    heapq.heappush(w, [0, N])
    for i in range(N-1, -1, -1):
        if S[i] == '0':
            while h:
                n, p = heapq.heappop(h)
                if p-i <= M:
                    heapq.heappush(h, [n+1, i])
                    heapq.heappush(w, [n+1, i])
                    heapq.heappush(h, [n, p])
                    break
            if len(h) == 0: return -1
        

    ans = []
    n, p = heapq.heappop(w)
    
    while w:
        m, q = heapq.heappop(w)
        if m == n + 1:
            ans.append(p-q)
            n = m
            p = q
    return " ".join(map(str, ans[::-1]))

if __name__ == '__main__':
    print(main())

Solution (Python):
inpl = lambda: list(map(int,input().split()))
N, M = inpl()
S = list(map(int,input()))
steps = [N]
i = N
while i > M:
    prev = i
    i -= M
    while S[i] > 0:
        i += 1
    if i >= prev:
        print(-1)
        exit()
    else:
        steps.append(i)
ans = []
cur = 0
while steps:
    prev = cur
    cur = steps.pop()
    ans.append(cur-prev)
print(' '.join(map(str,ans)))

Solution (Python):
n,m=map(int,input().split())
s=input()[::-1]
step=[]
proceed=0
while proceed<n:
  if s[proceed+1:min(proceed+m+1,n)]=="1"*m:
    print(-1);exit()
  else:
    check=proceed+m
    if s[min(check,n)]=="0":
      step.append(min(check,n)-proceed)
      proceed=min(check,n)
      
    else:
      while s[min(check,n)]=="1":
        if s[min(check,n)-1]=="0":
          step.append(min(check,n)-1-proceed)
          proceed=min(check,n)-1
          break
        
        check-=1
print(*step[::-1])

Solution (Python):
N,M = map(int,input().split())
S = input()
N0 = 2**(N-1).bit_length()
INF = 2**31-1


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


def query(l, r, data):
    L = l + N0; R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])

        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s



data1 = [INF]*(3*N0)
update(0,0,data1)
for n in range(N):
    if S[n+1]=='0':
        update(n+1,query(max(0,n-M+1),n+1,data1)+1,data1)

S = S[::-1]
data2 = [INF]*(3*N0)
update(0,0,data2)
for n in range(N):
    if S[n+1]=='0':
        update(n+1,query(max(0,n-M+1),n+1,data2)+1,data2)

cost1 = [INF]*(N+1)
cost2 = [INF]*(N+1)
for n in range(N+1):
    cost1[n] = query(n,n+1,data1)
    cost2[n] = query(N-n,N-n+1,data2)

ans = []
cost = 0
for n in range(N+1):
    if cost != cost1[n] and cost1[n]+cost2[n]==cost1[N]:
        ans.append(n)
        cost = cost1[n]
ans = [0]+ans
for i in range(len(ans)-2,-1,-1):
    ans[i+1] = ans[i+1]-ans[i]

ans = ' '.join([str(c) for c in ans[1:]])
if cost2[0]==INF:
    ans = '-1'
print(ans)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

import time
def Dijkstra(num, start, s, m):
    b = time.time()
    dist = [inf for i in range(num)]
    x = 0
    dist[0] = 0
    for i in range(num):
        if x > i:
            continue
        a = dist[i]
        for k in range(1, m + 1):
            if s[i + k] == "1":
                continue
            dist[i + k] = a + 1
            x = i + k
            if i + k == num - 1:
                return dist
        if x == i:
            x = inf
    return dist



def solve():
    n, m = LI()
    s = S()
    d = Dijkstra(n + 1, 0, s, m)
    if d[-1] == inf:
        print(-1)
        return
    ans = []
    q = deque([n])
    while q:
        a = q.pop()
        x = d[a]
        for i in range(min(a, m), 0, -1):
            if x - 1 == d[a - i]:
                q.append(a - i)
                ans.append(i)
                break
    ans = ans[::-1]
    print(" ".join(map(str, ans)))
    return



if __name__ == '__main__':
    solve()

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

import time
def Dijkstra(num, start, s, m):
    b = time.time()
    
    dist = [inf for i in range(num)]
    x = -1
    dist[0] = 0
    for i in range(num):
        if time.time() - b > 1:
            return dist
        if x > i:
            continue
        a = dist[i]
        for k in range(1, m + 1):
            if s[i + k] == "1":
                continue
            dist[i + k] = a + 1
            x = i + k
            if i + k == num-1:
                return dist
    
    return dist



def solve():
    n, m = LI()
    s = S()
    d = Dijkstra(n + 1, 0, s, m)
    if d[-1] == inf:
        print(-1)
        return
    ans = []
    q = deque([n])
    while q:
        a = q.pop()
        x = d[a]
        for i in range(min(a, m), 0, -1):
            if x - 1 == d[a - i]:
                q.append(a - i)
                ans.append(i)
                break
    ans = ans[::-1]
    print(" ".join(map(str, ans)))
    return



if __name__ == '__main__':
    solve()

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):
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])))