Harryxun/stf_run huggingface dataset:
#coding: utf-8
N = int(input())
l = []
for i in range(N):
    a = list(map(int, input().split()))
    if a[2] > 0:
      l.append(a)

for i in range(len(l)-1):
    ans = []
    for cx in range(101):
        for cy in range(101):
          if l[i][2] + abs(l[i][0] - cx) + abs(l[i][1] - cy) == l[i+1][2] + abs(l[i+1][0] - cx) + abs(l[i+1][1] - cy) and l[i][2] + abs(l[i][0] - cx) + abs(l[i][1] - cy) >= l[i][2] and l[i][2] + abs(l[i][0] - cx) + abs(l[i+1][1] - cy) >= l[i+1][2]:
            if i == 0:
              ans.append([cx, cy])
            else:
              if [cx, cy] in ansn:
                ans.append([cx, cy])
    ansn = ans[:]
    if len(ans) == 1:
        break
print(ans[0][0], ans[0][1], l[0][2] + abs(l[0][0] - ans[0][0]) + abs(l[0][1] - ans[0][1]))

### FIXED CODE ###

#coding: utf-8
N = int(input())
l = []
for i in range(N):
    a = list(map(int, input().split()))
    if a[2] > 0:
      l.append(a)
if len(l) >= 2:
    for i in range(len(l)-1):
        ans = []
        for cx in range(101):
            for cy in range(101):
                if l[i][2] + abs(l[i][0] - cx) + abs(l[i][1] - cy) == l[i+1][2] + abs(l[i+1][0] - cx) + abs(l[i+1][1] - cy) and l[i][2] != 0 and l[i+1][2] != 0:
                    if i == 0:
                        ans.append([cx, cy])
                    else:
                        if [cx, cy] in ansn:
                            ans.append([cx, cy])
        ansn = ans[:]
        if len(ans) == 1:
            break
    print(ans[0][0], ans[0][1], l[0][2] + abs(l[0][0] - ans[0][0]) + abs(l[0][1] - ans[0][1]))
else:
    print(l[0][0], l[0][1], l[0][2])
s = list(input())
if s[0] == 'Y' and s[1] == 'A' and s[2] == 'K' and s[3] == 'I':
    print('Yes')
else:
    print('No')


### FIXED CODE ###

s = list(input())
if len(s) < 4:
    print('No')
    exit()

if s[0] == 'Y' and s[1] == 'A' and s[2] == 'K' and s[3] == 'I':
    print('Yes')
else:
    print('No')
x,y = input().split()
x = int(x)
y = int(y)
while true:
    if x < y:
        print(y,x)
    if x > y:
        print(x,y)
    if x==0 and y==0:
        break
    


### FIXED CODE ###


while True:
    x,y = input().split()
    x = int(x)
    y = int(y)
    if x==0 and y==0:
        break
    elif x<y:
        print(x,y)
    elif x>=y:
        print(y,x)
##Just for prctice
n=int(input())

A=[int(i) for i in input().split()]

A.sort()
A.reverse()
a=0
b=0
for i in range(n):
    if i%2==0:
        a+=A[i]
    else:
        b+=A[i]

print(a-b)

"""
2
3 1

2

3
2 7 4

5

4
20 18 2 18

18
"""




### FIXED CODE ###


##Just for prctice
N=int(input())

A=int(input())

for i in range(A+1):
    if (N-i)%500==0:
        print("Yes")
        break
    elif i==A:
        print("No")


"""
2018
218

Yes

2763
0

No

37
514

Yes
"""
def main():
    to = ['T', 'G']
    fr = ['A', 'C']

    print(to[fr.index(input())])


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    to = ['T', 'G']
    fr = ['A', 'C']

    inc = input()

    try:
        print(to[fr.index(inc)])
    except Exception:
        print(fr[to.index(inc)])


if __name__ == "__main__":
    main()
N, M =map(int,input().split())
cards = list(map(int,input().split()))
card_pool = [list(map(int,input().split())) for _ in range(M)]
cards.sort()
#print(cards)
card_pool.sort(key=lambda x:x[1],reverse=True)
#print(card_pool)


ruisekiwa = 0
idx = 0
for i in range(M):
    for j in range(card_pool[i][0]):
        if card_pool[i][1] <= cards[idx]:
            print(sum(cards[idx:]) + ruisekiwa)
            break
        ruisekiwa += card_pool[i][1]
        idx += 1
        if idx == N:
            print(ruisekiwa)
            break
#print(sum(cards[idx:])+ruisekiwa)



### FIXED CODE ###

N,M = map(int,input().split())
*A, = map(int,input().split())
BC=[list(map(int,input().split())) for _ in [0]*M]
A.sort()
BC.sort(key=lambda x:-x[1])
i = 0
for B,C in BC:
    for j in range(i,min(N,i+B)):
        if A[j]<C:A[j]=C
    i = i+B
print(sum(A))
return input() * input()

### FIXED CODE ###

A, B = map(int,input().split())
print(A*B)
N,M = map(int, input().split())
am = list(map(int, input().split()))
c = [0,2,5,5,4,5,6,3,7,6]
f = [-1]*10010
f[0]=0
for i in range(1,N+1):
    for x in am:
        if i-c[x] >= 0:
            f[i] = max(f[i], f[i-c[x]]*10 +x)
            
print(f[n])

### FIXED CODE ###

N,M = map(int, input().split())
am = list(map(int, input().split()))
c = [0,2,5,5,4,5,6,3,7,6]
f = [-1]*10010
f[0]=0
for i in range(1,N+1):
    for x in am:
        if i-c[x] >= 0:
            f[i] = max(f[i], f[i-c[x]]*10 +x)
            
print(f[N])
n=int(input())
if n==1:print('Hello World')
a=int(input())
b=int(input())
else:print(a+b)

### FIXED CODE ###

n=int(input())
if n==1:print('Hello World')
else:
  a=int(input())
  b=int(input())
  print(a+b)
number=int(input())
hitpoint=list(map(int,input().split()))
xyz=[]
png=[]
m=min(hitpoint)
for i in range(len(hitpoint)):
    xyz.append(hitpoint[i]%2)
if hitpoint.count(hitpoint[0])==len(hitpoint):
    print(hitpoint[0])
elif hitpoint[len(hitpoint)]%m==0:
    for i in range(len(hitpoint)):
        png.append(hitpoint[i]%m)
    if png.count(0)==len(png):
        print(min(hitpoint))
    else:
        if hitpoint.count(1)!=0:
            print(1)
        elif xyz.count(0)!=len(xyz):
            print(1)
        elif xyz.count(1)==len(xyz):
            print(1)
        else:
            print(2)
elif hitpoint.count(1)!=0:
    print(1)
elif xyz.count(0)!=len(xyz):
    print(1)
elif xyz.count(1)==len(xyz):
    print(1)
else:
    print(2)

### FIXED CODE ###

n=int(input())
def gcd(x,y):
  if y==0:
    return x
  else:
    return gcd(y,x%y)
a=list(map(int,input().split()))
stack=a.pop()
for i in a:
  stack=gcd(i,stack)
print(stack)
def calculate(arr,M):
    sum = 0
    for i in range(M):
        index = 0
        value = 0
        for j in range(len(arr)):
            lastDay = i + 1
            if lastDay <= M:
                if arr[j][1] > value:
                    index = j
                    value = arr[j][1]

                if (arr[j][1] == value) and (arr[index][0] < arr[j][0]):
                        index = j
                        value = arr[j][i]

        if len(arr) > 0:
            sum += value
            arr.pop(index)

        if len(arr) == 0:
            break

    return sum

N, M = map(int, input().split())
arr = []
for i in range(N):
    day, mount = map(int, input().split())
    arr.append([day,mount])
result = calculate(arr,M)
print(result)

### FIXED CODE ###

from heapq import heappush, heappop
n, m = map(int, input().split())
jobs = {}
for _ in range(n):
  a, b = map(int, input().split())
  if a > m:
    continue
  if a in jobs:
    jobs[a].append(b)
  else:
    jobs[a] = [b]
result = 0
candidates = []
for a in range(1, m + 1):
  if a in jobs:
    for b in jobs[a]:
      heappush(candidates, -b)
  else:
    if len(candidates) == 0:
      continue
  result += -heappop(candidates)
print(result)
n=int(input())
a=list(map(int,input().split()))
a.sort()

c4=0
c2=0

for i in range(n):
    if a[i]%4==0:
        c4+=1
for i in range(n):
    if a[i]%4!=0 and a[i]%2==0:
        c2+=1

if c4==0:
    if all(a[i]%2==0 i in range(n)):
       print('Yes')
elif n<=2*c4 + c2:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

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

for i in range(n):
    if a[i]%4==0:
        c4+=1
for i in range(n):
    if a[i]%2==0:
        c2+=1

if n<=(2*c4 + max(1,c2-c4)):
    print('Yes')
else:
    print('No')
n = int(input());
s = input();

if n % 2 !== 0:
  print("No")
else:
  t = s[int(n/2) - 1]
  if t * 2 == s:
    print("Yes")
  else:
    print("No");
    


### FIXED CODE ###

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

if n % 2 != 0:
  print("No")
else:
  t = s[:int(n/2)]
  if t * 2 == s:
    print("Yes")
  else:
    print("No");
s,t = input().split()
if s in t:
    print('Yes')
else:
    print('No')
    

### FIXED CODE ###

s = input()
t = input()
if s == t[:-1]:
    print('Yes')
else:
    print('No')
x,a,b=map(int,input().split())

if b-a=<x and b-a<=0:
    print("delicious")
elif b-a<=x and b-a>0:
    print("safe")
else:
    print("dangerous")

### FIXED CODE ###

x,a,b=map(int,input().split())

if b-a<=x and b-a<=0:
    print("delicious")
elif b-a<=x and b-a>0:
    print("safe")
else:
    print("dangerous")
N, M = map(int, input().split())

A = sorted(list(map(int, input().split())), reverse=True)

B = []
for i in range(M):
    b, c = map(int, input().split())
    B.append([b, c])

B.sort(key=lambda x:(-x[1]))

cnt = 0
ans = 0
a = 0
b = 0
while True:
    if A[a] <= B[b][1]:
        for k in range(B[b][0]):
            ans += B[b][1]
            cnt += 1
            if cnt == N:
                print(ans)
                break
        b += 1
    else:
        cnt += 1
        ans += A[a]
        if cnt == N:
            print(ans)
            break
        a += 1

### FIXED CODE ###

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

A = sorted(list(map(int, input().split())), reverse=True)

B = []
for i in range(M):
    b, c = map(int, input().split())
    B.append([b, c])

B.sort(key=lambda x:(-x[1]))

cnt = 0
ans = 0
a = 0
b = 0
while True:
    if b <= M-1 and A[a] <= B[b][1]:
        n = min(B[b][0], N-cnt)
        ans += B[b][1]*n
        cnt += n
        if cnt == N:
            print(ans)
            break
        b += 1
    elif a <= N-1:
        cnt += 1
        ans += A[a]
        if cnt == N:
            print(ans)
            break
        a += 1
S = input()
lis = list(S)

for i in range(len(lis)):
    if i % 2 == 0:
        if lis[i] == 'R' or lis[i] == 'U' or lis[i] == 'D':
            flag_o = 1
        else:
            flag_o = 0
            break
    if i % 2 != 0:
        if lis[i] == 'L' or lis[i] == 'U' or lis[i] == 'D':
            flag_e = 1
        else:
            flag_e = 0
            break
        
if flag_o == 1 and flag_e == 1:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

S = input()
lis = list(S)
count = 0

for i in range(len(lis)):
    if i % 2 == 0:
        if lis[i] == 'R':
            count += 1
    if i % 2 != 0:
        if lis[i] == 'L':
            count += 1

    if lis[i] == 'U' or lis[i] == 'D':
        count += 1

if count == len(lis):
    print('Yes')
else:
    print('No')
coffee = input()

if coffee[2] = coffee[3] and coffee[4] = coffee[5]:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

coffee = input()

if coffee[2] == coffee[3] and coffee[4] == coffee[5]:
    print("Yes")
else:
    print("No")
import math
a,b,x = map(float,input().split())

c = a/(2*b-2*x/a**2)
d = (2*x)/(a*b**2)
if x/a >= a*b/2:
  result = math.atan(c)
else:result = math.degrees(math.atan(d))
print(result)

### FIXED CODE ###

import math
a,b,x = map(float,input().split())

c = (2*b-(2*x)/(a*a))/a
d = (a*b*b)/(2*x)
if x/a >= a*b/2:
  result = math.degrees(math.atan(c))
else:
  result = math.degrees(math.atan(d))
print(result)
N = int(input())

xyh1 = [] # h > 0
xyh2 = [] # h = 0
for _ in range(N) :
    x, y, h = map(int, input().split())
    if h > 0 :
        xyh1.append((x, y, h))
    else :
        xyh2.append((x, y, h))

def solve() :
    for Cx in range(0, 101) :
        for Cy in range(0, 101) :
            # 特定できるからxyh1は必ず1つは要素を持つ?
            x, y, h = xyh1[0]
            H = h + abs(x-Cx) + abs(y-Cy)
            
            flag = False
            for x, y, h in xyh1[1:] :
                if H != h + abs(x-Cx) + abs(y-Cy) :
                    flag = True
                    break
                    
            if flag :
                continue
                
            for x, y, h in xyh2 :
                if h + abs(x-Cx) + abs(y-Cy) > 0 :
                    flag = True
                    break
                    
            if flag :
                continue
                
            return (Cx, Cy, H)
            
print(*solve())

### FIXED CODE ###

N = int(input())

xyh1 = [] # h > 0
xyh2 = [] # h = 0
for _ in range(N) :
    x, y, h = map(int, input().split())
    if h > 0 :
        xyh1.append((x, y, h))
    else :
        xyh2.append((x, y, h))

def solve() :
    for Cx in range(0, 101) :
        for Cy in range(0, 101) :
            # 特定できるからxyh1は必ず1つは要素を持つ
            x, y, h = xyh1[0]
            H = h + abs(x-Cx) + abs(y-Cy)
            
            flag = False
            for x, y, h in xyh1[1:] :
                if H != h + abs(x-Cx) + abs(y-Cy) :
                    flag = True
                    break
                    
            if flag :
                continue
                
            for x, y, h in xyh2 :
                if H - abs(x-Cx) - abs(y-Cy) > 0 :
                    flag = True
                    break
                    
            if flag :
                continue
                
            return (Cx, Cy, H)
            
print(*solve())
N = int(input())
A = list(map(int, input().split()))
LIST = [0]*(10001)
sum = sum(A)
for i in A:
    LIST[i]+=1
Q = int(input())
b =[]
c =[]
for _ in range(Q):
    bs, cs = map(int, input().split())
    b.append(bs)
    c.append(cs)
for i in range(Q):
    LIST[c[i]]+=LIST[b[i]]
    sum+=LIST[b[i]]*(c[i]-b[i])
    LIST[b[i]]= 0
    print(sum)


### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
q = int(input())
num = [0] * 100010
b = [0] * q
c = [0] * q
for i in range(q):
    b[i], c[i] = map(int, input().split())

for i in a:
    num[i] += 1

s = sum(a)

for i in range(q):
    s += (c[i]-b[i])*num[b[i]]
    num[c[i]] += num[b[i]]
    num[b[i]] = 0
    print(s)
import math
import heapq
import sys
import re
from collections import Counter
import datetime
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN

#N,K=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
#x=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき


N=int(input())

print((2*N)//math.gcd(2,N))
    

### FIXED CODE ###

import math
import fractions
import heapq
import sys
import re
from collections import Counter
import datetime
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN

#N,K=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
#x=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき

N=int(input())
print((2*N)//fractions.gcd(2,N))
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

a, b = [0], [0]
for i in range(N):
　　a.append(a[i] + A[i])
for i in range(M):
　　b.append(b[i] + B[i])

ans, j = 0, M
for i in range(N + 1):
　　if a[i] > K:
　　　　break
　　while b[j] > K - a[i]:
　　　　j -= 1
　　ans = max(ans, i + j)
print(ans)

### FIXED CODE ###

import numpy as np


def main():
    N, M, K = map(int, input().split())
    A = np.array([0] + [int(i) for i in input().split()])
    B = np.array([0] + [int(i) for i in input().split()])

    A.cumsum(out=A)
    B.cumsum(out=B)

    ans = 0
    j = M
    for i in range(N + 1):
        if A[i] > K:
            break
        while B[j] + A[i] > K:
            j -= 1
        ans = max(ans, i + j)

    print(ans)


if __name__ == '__main__':
    main()
x,y = map(int,input().split())
ans = 0

if(y > 0):
    if(x > y):
        ans += 1
        ans += -y +x
    elif(x >= 0):
        ans += y -x
    elif(x > -y):
        ans += 1
        ans += y + x
    else:
        ans += 1
        ans += -y -x
else:
    if(x > -y):
        ans += 1
        ans += y + x
    elif(x >= 0):
        ans += 1
        ans += -y -x
    elif(x > y):
        ans += 1
        ans += -y +x
        ans += 1
    else:
        ans += y -x

if(x == 0 and y == 0) ans = 0
print(ans)


### FIXED CODE ###

x,y = map(int,input().split())
ans = 0
if(y > 0):
    if(x > y):
        ans += 1
        ans += -y +x
        ans += 1
    elif(x >= 0):
        ans += y -x
    elif(x > -y):
        ans += 1
        ans += y + x
    else:
        ans += 1
        ans += -y -x
else:
    if(x > -y):
        ans += 1
        ans += y + x
    elif(x >= 0):
        ans += 1
        ans += -y -x
    elif(x > y):
        ans += 1
        ans += -y +x
        ans += 1
    else:
        ans += y -x

if(x == 0 and y == 0):
    ans = 0
print(ans)
h,w,a,b= map(int,input().split()) 
mod=10**9+7
f=[1]
for i in range(h+w):
  f.append(f[i]*(i+1)%mod)
def comb(n,r,p):
  return f[n]*pow(f[r],p-2,p)*pow(f[n-r],p-2,p)%p
ans=0
for i in range(w-b):
  ans+=comb(h-a+b-1+i,b+i,mod)*comb(h+a-b-2-i,a-1,mod)%mod
print(ans%mod)
  

### FIXED CODE ###

h,w,a,b = map(int,input().split()) #入力
mod = 10**9+7 

#前計算　f[i] = i!
f=[1]
for i in range(h+w):
  f.append(f[i]*(i+1)%mod)

#C(n,r,p) = ( n! * r!^(p-2) * (n-r)!^(p-2) )%p
#pythonだとpow()で二分累乗法が使える
def comb(n, r, p):
  return f[n] * pow(f[r], p-2, p) * pow(f[n-r], p-2, p) % p

#紫点ごとに調べる
ans=0
for i in range(b, w):
  ans+= comb(h+i-a-1, i, mod) * comb(w-1-i+a-1, a-1, mod) % mod

print(ans%mod)
A, B, C, D, E, F = [int(n) for n in input().split()]

max_ratio = 0
for cnt_A in [n for n in range(30) if 100*A*n <= F]:
  for cnt_B in [n for n in range(30) if 100*A*cnt_A * 100*B*n <= F]:
    for cnt_C in [n for n in range(1500) if n*C <= E*(A*cnt_A+B*cnt_B) and 100*A*cnt_A + 100*B*cnt_B + n*C <= F]:
      for cnt_D in [n for n in range(1500) if n*D + C*cnt_C <= E*(A*cnt_A + B*cnt_B)and 100*A*cnt_A + 100*B*cnt_B + C*cnt_C + D*n <= F]:
        if (cnt_A!=0 or cnt_B !=0)and max_ratio < (C*cnt_C+D*cnt_D)/(100*A*cnt_A+100*B*cnt_B):
          max_ratio = (C*cnt_C + D*cnt_D)/(100*A*cnt_A+100*B*cnt_B)
          a = 100*A*cnt_A + 100*B*cnt_B
          b = C*cnt_C + D*cnt_D
print(a+b, b)


### FIXED CODE ###

A, B, C, D, E, F = [int(n) for n in input().split()]

max_ratio = -1
for cnt_A in [n for n in range(30) if 100*A*n <= F]:
  for cnt_B in [n for n in range(30) if 100*A*cnt_A * 100*B*n <= F]:
    for cnt_C in [n for n in range(1500) if n*C <= E*(A*cnt_A+B*cnt_B) and 100*A*cnt_A + 100*B*cnt_B + n*C <= F]:
      for cnt_D in [n for n in range(1500) if n*D + C*cnt_C <= E*(A*cnt_A + B*cnt_B)and 100*A*cnt_A + 100*B*cnt_B + C*cnt_C + D*n <= F]:
        if (cnt_A!=0 or cnt_B !=0)and max_ratio < (C*cnt_C+D*cnt_D)/(100*A*cnt_A+100*B*cnt_B):
          max_ratio = (C*cnt_C + D*cnt_D)/(100*A*cnt_A+100*B*cnt_B)
          a = 100*A*cnt_A + 100*B*cnt_B
          b = C*cnt_C + D*cnt_D
print(a+b, b)
import math
from functools import reduce
T = []
N = int(input())
for i in range(N):
    T.append(int(input()))


def lcm(a, b):
    g = math.gcd(a, b)
    return int(a / g * b)


x = T[0]
for i in range(1, N):
    x = lcm(x, T[i])

print(int(x))


### FIXED CODE ###

from functools import reduce
N = int(input())
T = []
for _ in range(N):
    T.append(int(input()))


def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


def lcm(a, b):
    if b > a:
        b, a = a, b
    return a * b // gcd(a, b)


x = reduce(lcm, T)
print(x)
def LI():
    return list(map(int,input().split()))
    
def OPEN():
    return map(int,open(0).read().split())

h,w,m=LI()
S=[[0]*w for i in range(h)]
a=[0]*h
b=[0]*w
for i in range(m):
    h,w=LI()
    
    S[h-1][w-1]+=1
    a[h-1]+=1
    b[w-1]+=1

# print(S)

    
now=0
ind_x=[]
ind_y=[]
# Ssumx=[sum(i) for i in S]
# SS=S.T
# Ssumy=[sum(i) for i in SS]



mx=max(a)
# max(Ssumx)
for i,j in enumerate(a):
    if j==mx:
        ind_x.append((i,j))
my=max(b)
# max(Ssumy)
for i,j in enumerate(b):
    if j==my:
        ind_y.append((i,j))
ans=0
for x,numx in ind_x:
    for y,numy in ind_y:
        if S[x][y]==0:
            tmp=numx+numy
        else:
            tmp=numx+numy-1

            
        ans=max(ans,tmp)
        
print(ans)


### FIXED CODE ###

h,w,m=map(int,input().split())
a=[0]*h
b=[0]*w
hw=[]
for _ in range(m):
    hh,ww=map(int,input().split())
    hw+=((hh-1,ww-1)),
    a[hh-1]+=1
    b[ww-1]+=1
    
ma=max(a)
mb=max(b)

# x_ind=[i for i,j in enumerate(a) if j==ma]
# y_ind=[i for i,j in enumerate(b) if j==mb]



cnt=0
# sonzai suru

for i,j in hw:
    if a[i]==ma and b[j]==mb:cnt+=1

if cnt==a.count(ma)*b.count(mb):
    print(ma+mb-1)
else:
    print(ma+mb)
A,P = map(int(input().split())

apple_cut = A * 3

apple_pie = (apple_cut + P) /2
                 
print(int(apple_pie))

### FIXED CODE ###

A,P = map(int,input().split())

apple_cut = A * 3

apple_pie = (apple_cut + P) /2
                 
print(int(apple_pie))
def solve():
    from heapq import heappush, heappop
    from sys import stdin
    #f_i = stdin
    f_i = open('146_F_in_s3')#
    
    N, M = map(int, f_i.readline().split())
    M *= -1
    S = f_i.readline().rstrip()
    
    unvisited = [True] * (N + 1)
    unvisited[N] = False
    rec = [[] for i in range(N + 1)]
    hq = [(0, N)] # (cost, pos)
    
    while hq:
        cost, pos = heappop(hq)
        if pos == 0:
            break
        
        cost += 1
        for r in range(M, 0):
            next_pos = pos + r
            if unvisited[next_pos] and S[next_pos] == '0':
                unvisited[next_pos] = False
                rec[next_pos] = [r] + rec[pos]
                heappush(hq, (cost, next_pos))
    else:
        return -1
    
    return ' '.join(str(-r) for r in rec[0])

print(solve())

### FIXED CODE ###

def solve():
    from collections import deque
    from sys import stdin
    f_i = stdin
    
    N, M = map(int, f_i.readline().split())
    S = f_i.readline().rstrip()
    
    M *= -1
    pos = N
    rec = deque()
    while pos:
        for move in range(M, 0):
            next_pos = pos + move
            if next_pos >= 0 and S[next_pos] == '0':
                pos = next_pos
                rec.appendleft(move)
                break
        else:
            print(-1)
            break
    else:
        print(' '.join(str(-move) for move in rec))

solve()
k, x = [int(x) for x in input().split()]
rl = max(-1000000, x - k + 1)
rr = min(+1000000, x + k - 1)
print(" ".join(range(rl, rr + 1)))

### FIXED CODE ###

k, x = [int(x) for x in input().split()]
rl = max(-1000000, x - k + 1)
rr = min(+1000000, x + k - 1)
print(*(range(rl, rr + 1)))
n = int(input())
i = 0
s = list()
while i<n:
    a = str(input())
    k = 0
    j = 0
    while k<i:
        if s[k] == a:
            j = 1
            break
        k+=1
    if j == 0:
        s.append(a)
    i+=1

print(len(s))


### FIXED CODE ###

n = int(input())
i = 0
s = set()
while i<n:
    s.add(str(input()))
    i+=1


print(len(s))
fa = [x for x in range (100002)]
ans = [-1 for i in range (100002)]
siz = [0 for i in range (100002)]
rank = [0 for i in range (100002)]


def find (x) : # find the highest ancestor of x
    fa[x] = x if fa[x] == x else find (fa[x])
    return fa[x]

def union (x, y) :
    fa[find (x)] = find (y)
    

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

for i in range (M) :
    a, b = list (map (int, input().split()))
    union (a, b)
    ans[a] -= 1
    ans[b] -= 1
    
# TODO : .... build ans[]
for i in range (1, N + 1) :
    siz[find(i)] += 1

for i in range (1, N + 1) :
    ans[i] += siz[find (i)]

# TODO : eliminate blockships
for i in range (K) :
    c, d = list (map (int, input().split()))
    if (find (c) == find (d)) :
        ans[c] -= 1
        ans[d] -= 1

print (' '.join (list (map(str , ans[1 : N + 1]))))

### FIXED CODE ###

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

fa = [x for x in range (n + 1)]
siz = [1 for i in range (n + 1)]
dep = [0 for i in range (n + 1)]
e = [1 for i in range (n + 1)]

def find (x) :
    if (fa[x] == x) :
        return x
    fa[x] = find (fa[x])
    return fa[x]

def uni (x, y) :
    u, v = find (x), find (y)
    if (dep[u] >= dep[v]) :
        fa[v] = u
        if (u != v) :
            siz[u] += siz[v]
        if (dep[u] == dep[v]) :
            dep[u] += 1
    else :
        fa[u] = v
        if (u != v) :
            siz[v] += siz[u]

for i in range (m) :
    a, b = list (map (int, input ().split ()))
    uni (a, b)
    e[a] += 1
    e[b] += 1

for i in range (1, n + 1) :
    siz[i] = siz[find (i)]

for i in range (k) :
    c, d = list (map (int, input ().split ()))
    if (find (c) == find (d)) :
        siz[c] -= 1
        siz[d] -= 1

siz = [siz[i] - e[i] for i in range (1, n + 1)]

print (' '.join (list (map (str, siz))))