Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

def merge(A, left, mid, right):

    n1 = mid-left
    n2 = right-mid
    L = [0 for i in range(n1+1)]
    R = [0 for i in range(n2+1)]
    for i in range(n1):
        L[i] = A[left+i]
    for i in range(n2):
        R[i] = A[mid+i]
    L[n1] = 10000000001
    R[n2] = 10000000001
    i = 0
    j = 0
    #global cnt
    cnt = 0
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i = i+1
            cnt +=1
        else:
            A[k] = R[j]
            j = j+1
            cnt +=1
    return cnt

def mergeSort(A, left, right):
    if left+1 < right:
         mid = (left+right) // 2
         cnt1 = mergeSort(A, left, mid)
         cnt2 = mergeSort(A, mid, right)
         cnt3 = merge(A, left, mid, right)
         return cnt1+cnt2+cnt3
    else:
        return 0

n = input()
A = list(map(int, input().split()))
cnt = mergeSort(A, 0, len(A))
print(*A)
print(str(cnt))

### FIXED CODE ###

def merge(A, left, mid, right):

    n1 = mid-left
    n2 = right-mid
    #L = [0 for i in range(n1+1)]
    #R = [0 for i in range(n2+1)]
    #for i in range(n1):
    #    L[i] = A[left+i]
    #for i in range(n2):
    #    R[i] = A[mid+i]
    L = A[left:mid]
    R = A[mid:right]
    L.append(float('inf'))
    R.append(float('inf'))
    i = 0
    j = 0
    global cnt

    for k in range(left, right):
        cnt += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i = i+1
        
        else:
            A[k] = R[j]
            j = j+1
    return cnt

def mergeSort(A, left, right):
    if left+1 < right:
         mid = (left+right) // 2
         mergeSort(A, left, mid)
         mergeSort(A, mid, right)
         merge(A, left, mid, right)
    else:
        return 0

n = input()
A = list(map(int, input().split()))
cnt = 0
mergeSort(A, 0, len(A))
print(*A)
print(str(cnt))
### BUGGY CODE ###

import math
N, X, Y = list(map(int, input().split()))

x = []
for i in range(1, N + 1):
    for j in range(1, N + 1):
        if i >= j:
            continue
        if i == X and Y == j:
            x.append(1)
        else:
            x.append(int(min(j - i, math.fabs(X - i) + math.fabs(Y - j) + 1)))

for i in range(1, N):
    print(x.count(i))


### FIXED CODE ###

N, X, Y = list(map(int, input().split()))
res = [0] * N
for i in range(1, N + 1):
    for j in range(1, N + 1):
        if i >= j:
            continue
        if i == X and Y == j:
            key = 1
        else:
            key = int(min(j - i, abs(X - i) + abs(Y - j) + 1))
        res[key] += 1

for i in range(1, N):
    print(res[i])
### BUGGY CODE ###

import bisect
n=int(input())
l=list(map(int, input().split()))
l.sort()
ans=0
for i in range(n-2):
    for j in range(i+1,n-1):
        ans+=bisect.bisect_left(l[j+1:],l[i]+l[j])
print(ans)

### FIXED CODE ###

import bisect
n=int(input())
l=list(map(int, input().split()))
l.sort()
ans=0
for i in range(n-2):
    for j in range(i+1,n-1):
        ans+=bisect.bisect_left(l[j+1:],l[i]+l[j])
print(ans)
### BUGGY CODE ###

import numpy as np

L,R = map(int, input().split())

if  R-L > 2018:
    print(0)
    
else:
    ans = 2018
    
    R = R % 2019
    L = L % 2019

    if L > R:
        R += 2019
        
    if R - L > 1000:
        print(1)
        
    for i in np.arange(L, R+1):
        for j in np.arange(i+1, R+1):
            i = i % 2019
            j = j % 2019
            k = i * j % 2019
            ans = np.amin(np.array([k, ans]))
            
    print(ans)    

### FIXED CODE ###

import numpy as np

L,R = map(int, input().split())

if  R-L > 2018:
    print(0)
    
else:
    ans = 2018
    
    R = R % 2019
    L = L % 2019

    if L > R:
        R += 2019
        
    if R - L > 500:
        print(0)
        
    else:
        for i in np.arange(L, R+1):
            for j in np.arange(i+1, R+1):
                i = i % 2019
                j = j % 2019
                k = i * j % 2019
                ans = np.amin(np.array([k, ans]))
            
        print(ans)
### BUGGY CODE ###

def main():
    INF = 10**9
    H,N = map(int,input().split())
    A,B = [0]*N,[0]*N
    for i in range(N):
        A[i],B[i] = map(int,input().split())
    dp = [INF]*(H+max(A)+1)
    dp[0] = 0
    for i in range(H):
        if dp[i] == INF:
            continue
        else:
            for j in range(N):
                if dp[i]+B[j] < dp[i+A[j]]:
                    dp[i+A[j]] = dp[i]+B[j]
    print(min(dp[H:]))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    H,N = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    maxA = max(A for A,B in AB)
    dp = [0]*(H+maxA)
    for i in range(0,H+maxA):
        if i <= 0:
            dp[i] = 0
        else:
            dp[i] = min(dp[i-A]+B for A,B in AB)
    print(min(dp[H:]))


if __name__ == '__main__':
    main()
### BUGGY CODE ###

from collections import Counter


def main():
    N = int(input())
    A = list(map(int, input().split()))

    A_set = set(A)
    A_dict = Counter(A)

    for key, count in A_dict.items():
        if count > 1:
            A_set.discard(key)

        k = key * 2
        while k <= max(A):
            A_set.discard(k)
            k += key

    print(len(A_set))


if __name__ == '__main__':
    main()


### FIXED CODE ###


def main():
    N = int(input())
    A = list(map(int, input().split()))

    m = max(A) + 1
    dp = [0] * m

    for a in sorted(A):
        if dp[a] != 0:
            dp[a] = 2
            continue
        for i in range(a, m, a):
            dp[i] += 1

    print(sum(dp[i] == 1 for i in A))


if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())
seq = list(map(int, input().split()))
a = 10 ** 9 + 7
res = 0
i = 0
j = 1
for i in range(n - 1):
  for j in range(i + 1, n):
    b = seq[i] * seq[j]
    if a < b:
      res += (seq[i] * seq[j]) % (10 ** 9 + 7)
    else:
      res = res + b - a
print(res % (10 ** 9 + 7))

### FIXED CODE ###

n = int(input())
seq = list(map(int, input().split()))
a = 10 ** 9 + 7
s = sum(seq)
res = 0
for i in range(n - 1):
  s -= seq[i]
  res += (seq[i] * s) % a
print(res % a)
### BUGGY CODE ###

import sys

input = sys.stdin.readline

def main():
    ans = 0
    mod = (10**9)+7
    n = int(input())
    a = list(map(int, input().split()))
    for i in range(n-1):
        for j in range(i+1, n):
           ans += (a[i]%mod*a[j]%mod)%mod
    print(ans%mod)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys

input = sys.stdin.readline

def main():
    ans = 0
    mod = (10**9)+7
    n = int(input())
    a = list(map(int, input().split()))
    suma = sum(a)
    for i in range(n-1):
        suma -= a[i]
        ans += a[i]*suma
    print(ans%mod)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

limit, sum_xyz = map(int, input().split())

pair = list()

for x in range(limit + 1):
    y_limit = 0
    for y in range(limit + 1):
        z = sum_xyz - x - y
        if z < 0 or z > limit:
            continue
        pair.append([x, y, z])
ans = len(pair)

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
def main():
    K,S = [int(x) for x in input().split()]
 
    count = 0
 
    for x in range(K+1):
        for y in range(K+1):
            z = S - (x + y)
            if z >= 0 and z <= K:
                count += 1
 
    print(count)
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

# ABC141d
import sys
import heapq
import math
import fractions
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

a, b = map(int, input().split())
cd = []
for i in range(1, fractions.gcd(a, b) + 1):
    if (a % i != 0 or b % i != 0):
        continue
    flag = True
    for j in cd:
        if (j == 1):
            continue
        if (i % j == 0):
            flag = False
            break
    if (flag):
        cd.append(i)
print(len(cd))

### FIXED CODE ###

# ABC141d
import sys
import heapq
import math
import fractions
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

a, b = map(int, input().split())
cd = []


def prime_decomposition(n):
    i = 2
    table = set()
    while i * i <= n:
        while n % i == 0:
            n /= i
            table.add(i)
        i += 1
    if n > 1:
        table.add(n)
    return table


print(len(prime_decomposition(a).intersection(prime_decomposition(b)))+1)
exit()

for i in range(1, fractions.gcd(a, b) + 1):
    if (a % i != 0 or b % i != 0):
        continue
    flag = True
    for j in cd:
        if (j == 1):
            continue
        if (i % j == 0):
            flag = False
            break
    if (flag):
        cd.append(i)
print(len(cd))
### BUGGY CODE ###

import itertools

K,S=map(int,input().split())
combi=[]
num=0
for i in range(K+1):
    for j in range(K+1):
        if 0<=S-i-j<=K:
            combi=[i,j,S-i-j]
            #print(combi)
            #print(set(itertools.permutations(combi)))
            num+=1
print(num)

### FIXED CODE ###

K,S=map(int,input().split())
num=0
for i in range(K+1):
    for j in range(K+1):
        if 0<=S-i-j<=K:
            num+=1
print(num)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]
dij=[(1,0),(0,1),(-1,0),(0,-1)]

def main():
    h,w=MI()
    ss=[SI() for _ in range(h)]

    def dfs(i,j):
        bc=ss[i][j]=="#"
        wc=ss[i][j]=="."
        for di,dj in dij:
            ni,nj=i+di,j+dj
            if ni<0 or nj<0 or ni>=h or nj>=w:continue
            if fin[ni][nj] or ss[i][j]==ss[ni][nj]:continue
            fin[ni][nj]=True
            ret=dfs(ni,nj)
            bc+=ret[0]
            wc+=ret[1]
        return bc,wc

    ans=0
    fin=[[False]*w for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if fin[i][j] or ss[i][j]==".":continue
            fin[i][j]=True
            bc,wc=dfs(i,j)
            ans+=bc*wc
    print(ans)

main()

### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]
dij=[(1,0),(0,1),(-1,0),(0,-1)]

def main():
    h,w=MI()
    ss=[SI() for _ in range(h)]

    def dfs(i,j):
        stack=[(i,j)]
        bc,wc=0,0
        while stack:
            i,j=stack.pop()
            if ss[i][j]=="#":bc+=1
            else:wc+=1
            for di,dj in dij:
                ni,nj=i+di,j+dj
                if ni<0 or nj<0 or ni>=h or nj>=w:continue
                if fin[ni][nj] or ss[i][j]==ss[ni][nj]:continue
                fin[ni][nj]=True
                stack.append((ni,nj))
        return bc,wc

    ans=0
    fin=[[False]*w for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if fin[i][j]:continue
            fin[i][j]=True
            bc,wc=dfs(i,j)
            ans+=bc*wc
    print(ans)

main()
### BUGGY CODE ###

from functools import lru_cache
#@lru_cache(maxsize=1000)
N = int(input())
S =input()
a = 0
for i in range(N-2):
  for j in range(i,N-1):
    for k in range(j,N):
      if S[i] != S[j] and S[i] != S[k] and S[k] != S[j] and j -i != k-j:
        a+= 1
print(a)

### FIXED CODE ###

n = int(input())
s = input()

r = 0
g = 0
b = 0


for ss in s:
    if ss == "R":
        r += 1
    elif ss == "G":
        g += 1
    elif ss == "B":
        b += 1
ng = 0
i = 0
while i < n:
    j = 1
    while i+2*j < n:
        if s[i] != s[i+j] and s[i+j] != s[i+2*j] and s[i] != s[i+2*j]:
            ng += 1
        j += 1
    i += 1
print(r*g*b-ng)
### BUGGY CODE ###

N = int(input())
S = input()
dp = [[0]*N for i in range(N)]
pm = 0
ans = 0
for i in range(N-1,0,-1):
  for j in range(i-1,-1,-1):
    if S[i]==S[j]:
      if i<N-1:
        dp[i][j] = min(dp[i+1][j+1]+1, i-j)
      else:
        dp[i][j] = 1
    else:
      dp[i][j] = 0
    if dp[i][j]>ans:
      ans = dp[i][j]
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
dp = [[0]*N for i in range(N)]
pm = 0
ans = 0
for i in range(N-1,0,-1):
  for j in range(i-1,-1,-1):
    if S[i]==S[j]:
      if i<N-1:
        dp[i][j] = min(dp[i+1][j+1]+1, i-j)
      else:
        dp[i][j] = 1
    else:
      dp[i][j] = 0
    if dp[i][j]>ans:
      ans = dp[i][j]
print(ans)
### BUGGY CODE ###

import sys
import numpy as np
import math

input = sys.stdin.readline


def solve():
    infinity = 10 ** 10
    n, m, le = map(int, input().split())
    paths = np.zeros((n, n))
    for i in range(n):
        for j in range(n):
            if i != j:
                paths[i, j] = infinity

    for _ in range(m):
        a, b, c = map(int, input().split())
        paths[a - 1, b - 1] = c
        paths[b - 1, a - 1] = c

    for k in range(n):
        for i in range(n):
            for j in range(n):
                paths[i, j] = min(paths[i, j], paths[i, k] + paths[k, j])

    refuels = np.array(paths, copy=True)
    for i in range(n):
        for j in range(n):
            refuels[i, j] = 1 if refuels[i, j] <= le else infinity
            if i == j:
                refuels[i, j] = 0

    for k in range(n):
        for i in range(n):
            for j in range(n):
                refuels[i, j] = min(refuels[i, j], refuels[i, k] + refuels[k, j])

    q = int(input())
    for _ in range(q):
        s, t = map(int, input().split())
        print(int(refuels[s-1, t-1] - 1 if refuels[s-1, t-1] < infinity else -1))


if __name__ == "__main__":
    solve()


### FIXED CODE ###


from scipy.sparse.csgraph import floyd_warshall
import numpy as np

N, M, L = map(int, input().split())
graph = np.full((N, N), 10 ** 10)
for _ in range(M):
    s, t, w = map(int, input().split())
    if w <= L:
        graph[s - 1][t - 1] = graph[t - 1][s - 1] = w
graph = floyd_warshall(graph, directed=False)
graph = floyd_warshall(graph <= L, directed=False)
graph[np.isinf(graph)] = 0

Q = int(input())
ans = []
for _ in range(Q):
    s, t = map(int, input().split())
    ans.append(int(graph[s - 1][t - 1]) - 1)
print(*ans, sep='\n')
### BUGGY CODE ###

i = input().split()
a = int(i[0])
b = int(i[1])
k = int(i[2])

for n in range(k):
  if a >= 1:
    a -= 1
  elif b >= 1:
    b -= 1
  else:
    break
print(a,b)

### FIXED CODE ###

i = input().split()
a = int(i[0])
b = int(i[1])
k = int(i[2])
c = a 
d = b

if k >= a+b:
  c = d = 0

elif k == a:
  c = 0

elif k > a:
  c = 0
  d = b - (k - a)

else:
  c = a - k
  
print(c,d)
### BUGGY CODE ###

import collections
import math

n = int(input())

f_list = [[]]*(10**7+1) # すべて素数扱い
ans = [1]*(10**7+1)

def get_ans(t):
    c = collections.Counter(t)
    v_list = c.values()
    ans = 1
    for v in v_list:
        ans *= v+1
    return ans

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

for i in range(2, n+1):
    tmp = [] # 約数のリスト
    if is_prime(i):
        tmp = [i]
    elif i % 2 == 0:
        tmp = f_list[i//2].copy()
        tmp.append(2)
    else:
        f = 3
        while f*f <= i:
            if i % f == 0:
                tmp = f_list[i//f].copy()
                tmp.append(f)
                break
            else:
                f += 2
    f_list[i] = tmp
    ans[i] = i*get_ans(tmp)
print(sum(ans[1:n+1]))


### FIXED CODE ###

import collections
import math

n = int(input())
ans = 0

for i in range(1,n+1):
    tail = (n // i)
    ans += (tail)*(tail+1)//2*i
print(ans)
### BUGGY CODE ###

n, p = map(int, input().split())
s = input()
count = 0
if p in {2, 5}:
    for right in range(n):
        if int(s[right]) % p == 0:
            count += (right + 1)
else:
    mod_p_count = [0 for i in range(p)]
    mod_p_count[0] = 1
    for pow in range(1, n + 1):
        sub_s = int(s) % 10**pow
        mod_p_count[sub_s % p] += 1
    for i in mod_p_count:
        count += i*(i - 1) // 2
print(count)

### FIXED CODE ###

n, p = map(int, input().split())
s = input()
sum_count = 0
if p in {2, 5}:
    for right in range(n):
        if int(s[right]) % p == 0:
            sum_count += (right + 1)
else:
    modp_count = [0] * p
    modp_count[0] = 1
    subs_modp, pow = 0, 1
    for si in s[::-1]:
        subs_modp += ((int(si)*pow) % p)
        subs_modp %= p
        modp_count[subs_modp] += 1
        pow = (pow*10) % p
        
    for count in modp_count:
        sum_count += count*(count - 1) // 2
print(sum_count)
### BUGGY CODE ###

N = int(input())
l = []
for i in range(N):
  l.append(input())
s = []
w = []
for i in range(N):
    s.append(l.count(l[i]))
    w.append(l[i])
MAX = max(s)
g = []
for i in range(len(s)):
  if s[i] == MAX:
    g.append(w[i])
h = set(g)
j = list(h)
j.sort()
for i in range(len(j)):
  print(j[i])

### FIXED CODE ###

from collections import Counter
n = int(input())
l = []
for i in range(n):
  l.append(input())
c = Counter(l)
t = c.most_common()
x = 0
ans = []
for k,v in t:
  if x <= v:
    ans.append(k)
    x = v
ans.sort()
for i in range(len(ans)):
  print(ans[i])
### BUGGY CODE ###

MOD = 998244353
N, S = map(int, input().split())
A = list(map(int, input().split()))
DP = [[0] * (1 + S) for _ in range(1 + N)]  # DP[i][j] はi番目までみた時に総和がjと成る組み合わせの総和
# 初期化
DP[0][0] = 1
# 漸化式　DP[i][j] = DP[i-1][j]*2 + DP[i-1][j-A[i]]
for i in range(1, N + 1):
    for j in range(S + 1):
        if j >= A[i - 1]:
            DP[i][j] = DP[i - 1][j] * 2 + DP[i - 1][j - A[i - 1]]
        else:
            DP[i][j] = DP[i - 1][j] * 2
        DP[i][j] %= MOD
print(DP[N][S])


### FIXED CODE ###

MOD = 998244353
N, S = map(int, input().split())
A = list(map(int, input().split()))
DP = [[0] * (1 + S) for _ in range(1 + N)]  # DP[i][j] はi番目までみた時に総和がjと成る組み合わせの総和
# 初期化
DP[0][0] = 1
# 漸化式　DP[i][j] = DP[i-1][j]*2 + DP[i-1][j-A[i]]
for i in range(1, N + 1):
    for j in range(S + 1):
        if j >= A[i - 1]:
            DP[i][j] = DP[i - 1][j] * 2 + DP[i - 1][j - A[i - 1]]
        else:
            DP[i][j] = DP[i - 1][j] * 2
        DP[i][j] %= MOD
print(DP[N][S])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))

a_set = sorted(set(a))
a_dict = {}
cnt_dict = {}


def f(n):
    sum = 0
    for i in range(n):
        sum += i
    return sum


sum = 0
for i in a_set:
    cnt_dict[i] = a.count(i)
    sum += f(cnt_dict[i])


for i in a_set:
    a_dict[i] = sum - (cnt_dict[i] - 1)


for i in a:
    print(a_dict[i])

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))

# a_set = sorted(set(a))

count = [0] * (n + 1)


def f(n):
    return (n * (n - 1) // 2)


sum = 0
for i in a:
    count[i] += 1
for i in count:
    sum += f(i)

for i in a:
    print(sum - (count[i] - 1))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10000000)

class tree:
    def __init__(self):
        self.baby_list=[]
        self.counter=0
    
    def add_value(self):
        for i in self.baby_list:
            hoge[i].counter += self.counter
            hoge[i].add_value()

N,Q=list(map(int, input().split() ))


hoge={}

for i in range(1,N+1):
    hoge[i] = tree()
    
for i in range(N-1):
    a,b=list(map(int, input().split() ))
    hoge[a].baby_list.append(b)

for i in range(Q):
    root, value = list(map(int, input().split() ))
    hoge[root].counter+=value

hoge[1].add_value()
output = []
for t in hoge:
    output.append(hoge[t].counter)

output = list(map(str, output))
print(" ".join(output))

### FIXED CODE ###

import sys

sys.setrecursionlimit(10000000)


N,Q=list(map(int, input().split() ))

data={i+1:0 for i in range(N)}

# for i in range(N-1):
#     a,b=list(map(int, input().split() ))
#     hoge[a].baby_list.append(b)

relate = [list(map(int, input().split() )) for i in range(N-1)]
relate.sort(key=lambda x :x[0])
    
for i in range(Q):
    root, value = list(map(int, input().split() ))
    data[root]+=value

for a,b in relate:
    data[b]+=data[a]

print(" ".join(list(map(str,list(data.values())))))
### BUGGY CODE ###

s=list(input())
c=i=0
while i<len(s)-1:
	t,u=s[i],s[i+1]
	if t>=u:i+=1
	else:
		t,u=u,t
		c+=1
		if i>1:i-=1
print(c)

### FIXED CODE ###

s=input()
r=w=0
for c,i in zip(s,range(len(s))):
	if c=='W':
		r+=i-w
		w+=1
print(r)
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-


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

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

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

      if values[j] is not None:
        break

      values[j] = i

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

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

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

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


if __name__ == '__main__':
  main()


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-


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

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

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

      if values[j] is not None:
        break

      values[j] = i

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

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

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

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


if __name__ == '__main__':
  main()