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

class Puzzle:
    def __init__(self,panel,space,cnt):
        self.panel=panel
        self.space=space
        self.cnt=cnt

d=(1,-1,4,-4)

def check(s):
    if s==map(str,range(8)):
        return True
    return False

def bfs(s):
    m=set()
    que=[]
    que.append(s)
    m.add(tuple(s.panel))
    while que!=[]:
        now=que[0]
        del que[0]
        if check(now.panel):
            return now.cnt
        idx1=now.space
        for i in range(4):
            idx2=idx1+d[i]
            if idx2<0 or idx2>7:
                continue
            if (idx1==3 and d[i]==1) or (idx1==4 and d[i]==-1):
                continue
            next_panel=now.panel[:]
            next_panel[idx2],next_panel[idx1]=now.panel[idx1],now.panel[idx2]
            next=Puzzle(next_panel,idx2,now.cnt+1)
            if tuple(next.panel) not in m:
                m.add(tuple(next.panel))
                que.append(next)
    return -1

while True:
    try:
        panel=raw_input().split()
    except EOFError:
        break
    space=panel.index("0")
    s=Puzzle(panel,space,0)
    ans=bfs(s)
    print ans

### FIXED CODE ###

from collections import defaultdict
d=(1,-1,4,-4)

def solve():
    que=["01234567"]
    while que!=[]:
        v=que[0]
        del que[0]
        pos=v.index("0")
        for i in range(4):
            idx2=pos+d[i]
            if idx2<0 or idx2>7:
                continue
            if (pos==3 and d[i]==1) or (pos==4 and d[i]==-1):
                continue
            u=list(v)
            u[pos],u[pos+d[i]]=u[pos+d[i]],u[pos]
            u="".join(u)
            if res[u]==0:
                que.append(u)
                res[u]=res[v]+1
res=defaultdict(int)
res["01234567"]=1
solve()
while True:
    try:
        s=raw_input().split()
    except EOFError:
        break
    s="".join(s)
    print res[s]-1
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
k = 1
flag = True
for i in a:
  k *= i
  
if k > 10 ** 18:
  print(-1)
  flag = False
if flag:
  print(k)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
k = 1
flag = True
for i in a:
  k *= i  
  if k > 10 ** 18:
    flag = False
    break

if 0 in a:
  print(0)
elif flag:
  print(k)
else:
  print(-1)
### BUGGY CODE ###

D, G=list(map(int, input().split()))
#L[i][0]:i番目の問題数、L[i][0]:i番目のボーナス得点 調整のため[0]追加
L=[0]+[list(map(int, input().split())) for i in range(D)]
#f:i番目まで考えるときの最小問題数  
def f(G, i):
    l=[]
    if i==0:
        return 1000
    else:
    #j:i番目の問題を解く数
        for j in range(min(G//(i*100), L[i][0])+1):
            g=G-j*i*100
            #i番目でボーナス獲得し、足りない点数をi-1番目までで補うとき
            if j==L[i][0] and g-L[i][1]>0:
                l.append(f(g-L[i][1],i-1)+j)
            #i番目でボーナス獲得し、それで点数が足りる時
            elif j==L[i][0] and g-L[i][1]<=0:
                l.append(L[i][0])
            #i番目でボーナス獲得せず、足りない点数をi-1番目までで補うとき
            elif g>0:
                l.append(f(g,i-1)+j)
            #i番目でボーナス獲得せず、それで点数が足りる時
            elif g<=0:
                l.append(j)
                break
        return min(l)
print(f(G,D))

### FIXED CODE ###

D, G=list(map(int, input().split()))
#L[i][0]:i番目の問題数、L[i][0]:i番目のボーナス得点
L=[0]+[list(map(int, input().split())) for i in range(D)]
 
#f:i番目まで考えるときの最小問題数  
def f(G, i):
    if i==0:
	    return 10000
    #n:i番目を絶対に解くときの問題数  
    n=min(G//(i*100), L[i][0])
    #s:i番目を絶対に解くときのスコア  
    s=n*i*100
    #全部解くとき、ボーナスもスコアに加える
    if n==L[i][0]:
        s+=L[i][1]
	#スコアに届かない時、届かない分はG-s点をi-1番目までで埋める
    if s<G:
        n+=f(G-s, i-1)
    #i-1番目までの方が少ない時はそっちを返す
    return min(n, f(G,i-1))
print(f(G, D))
### BUGGY CODE ###

def F(a, b):
    count = 0
    c = max(a, b)
    while c > 9:
        c = c / 10
        count += 1
    return count+1

N = int(input())
minimum = 11
for num in range(1,int(N/100)+101):
    if N % num == 0:
        minimum = min(minimum, F(num, N/num))
print(minimum)

### FIXED CODE ###

def F(a, b):
    count = 0
    c = max(a, b)
    while c >= 10:
        c = c / 10
        count += 1
    return count+1

N = int(input())
minimum = 15
for num in range(1,int(N/(10**5))+10**5+1):
    if N % num == 0:
        minimum = min(minimum, F(num, N/num))
print(minimum)
### BUGGY CODE ###

import sys
input  = sys.stdin.readline

N,K = map(int,input().split())
hn = list(map(int,input().split()))
rtn = [0]*N
for i in range(N):
  if i==0:
    rtn[i]=0
  else:
    rtn[i]=rtn[i-1]+abs(hn[i]-hn[i-1])
    for j in range(K):
      if i>j:
        rtn[i]=min(rtn[i], rtn[i-j-1]+abs(hn[i]-hn[i-j-1]))
      else:
        break
print(rtn[N-1])

### FIXED CODE ###

n,k=map(int,input().split())
H=list(map(int,input().split()))
 
dp=[float('inf') for _ in range(n)]
dp[0]=0
for i,hi in enumerate(H[1:],1):
  s=max(0,i-k)
  dp[i]=min([aj + abs(hi-hj) for hj,aj in zip(H[s:i],dp[s:i])])
print(dp[-1])
### BUGGY CODE ###

r,g,b,n = map(int,input().split())
count = 0
for i in range(n+1):
    for j in range(n+1):
        bk = n-i*r-j*g
        if bk%b == 0 and bk >= 0:
            count += 1
print(count)

### FIXED CODE ###

r,g,b,n = map(int,input().split())
count = 0
for i in range(n+1):
    for j in range(n+1):
        bk = n-i*r-j*g
        if bk%b == 0 and bk >= 0:
            count += 1
print(count)
### BUGGY CODE ###

import bisect
while True:
    n,S = map(int, raw_input().split())
    if n == 0 and S == 0:
        break
    r = [input() for i in range(n)]
    ans = 0
    r.sort()
    for i in range(n):
        tmp = S - r[i] + 1
        if (tmp <= 0):
            ans += n - 1
        else:
            d = r[0:i] + r[i + 1:]
            index = bisect.bisect_right(d, tmp)
            ans += index
    print ans / 2

### FIXED CODE ###

import bisect
while True:
    n,S = map(int, raw_input().split())
    if n == 0 and S == 0:
        break
    r = [input() for i in range(n)]
    ans = 0
    r.sort()
    for i in range(n):
        tmp = S - r[i] + 1
        if (tmp <= 0):
            ans += n - 1
        else:
            index = bisect.bisect_left(r, tmp)
            if (index <= i):
                ans += n - index - 1
            else:
                ans += n - index
    print ans / 2
### BUGGY CODE ###

N,Q = map(int,input().split())
AB = [[] for _ in range(N-1)]
for n in range(N-1):
    AB[n] = list(map(int,input().split()))
PX = [[] for _ in range(Q)]
for q in range(Q):
    PX[q] = list(map(int,input().split()))
graph = [[] for _ in range(N+1)]
for ab in AB:
    graph[ab[0]].append(ab[1])
    graph[ab[1]].append(ab[0])
val = [0] * (N+1)
for px in PX:
    val[px[0]] += px[1]
parent = [0] * (N+1)
from collections import deque
Q  = deque([1])
while Q:
    q = Q.pop()
    for c in graph[q]:
        if c == parent[q]:
            continue
        parent[c] = q
        Q.append(c)
        val[c] += val[q]
print(*val[1:])

### FIXED CODE ###

N,Q = map(int,input().split())
AB = [[] for _ in range(N-1)]
for n in range(N-1):
    AB[n] = list(map(int,input().split()))
PX = [[] for _ in range(Q)]
for q in range(Q):
    PX[q] = list(map(int,input().split()))
graph = [[] for _ in range(N+1)]
for ab in AB:
    graph[ab[0]].append(ab[1])
    graph[ab[1]].append(ab[0])
val = [0] * (N+1)
for px in PX:
    val[px[0]] += px[1]
parent = [0] * (N+1)
from collections import deque
Q  = deque([1])
while Q:
    q = Q.popleft()
    for c in graph[q]:
        if c == parent[q]:
            continue
        parent[c] = q
        Q.append(c)
        val[c] += val[q]
print(*val[1:])
### BUGGY CODE ###

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

a.sort()
for i in range(1,n):
    tem = a.count(i)
    print(tem)
    a = a[tem:]

print(0)

### FIXED CODE ###

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

a.sort()
a = collections.deque(a)
counter = 0
for i in range(1, n+1):
    while len(a) != 0:
        if i != a[0]: 
            break
        counter += 1
        a.popleft()    
    print(counter)
    counter = 0
### BUGGY CODE ###

import sys

def mink(numk,l):
    x = 1
    for _ in range(k):
        x = a[x-1]
    return x

input = sys.stdin.readline
n,k = map(int,input().split())
a = list(map(int,input().split()))

# kが小さい時
if k <= 10**10:
    print(mink(k,a))
    sys.exit()

z = 1
p = [1]
for _ in range(k):
    z = a[z-1]
    if z in p:
        p.append(z)
        break
    p.append(z)

# 周期の来る前の回数
num = p.index(p[-1])

p = p[num:]

# 周期
pn = len(p)-1

k -= num

# 回数/周期のあまり
anum = k%pn
print(p[anum])


### FIXED CODE ###

import sys

input = sys.stdin.readline
n,k = map(int,input().split())
a = list(map(int,input().split()))

p = [1]
for i in range(n):
    p.append(a[p[i]-1])

if k <= n:
    print(p[k])
else:
    # 周期の来る前の回数
    num = p.index(p[-1])
    p = p[num:]

    # 周期
    pn = len(p)-1
    k -= num

    # 回数/周期のあまり
    ans = k%pn
    print(p[ans])
### BUGGY CODE ###

n = int(input())
a_ls = list(map(int, input().split()))
a_ls.sort()

ans = 0
for i in range(n):
    not_divisible = True
    for j in range(i):
        if a_ls[i] % a_ls[j] == 0:
            not_divisible = False
        if a_ls[i]//2 < a_ls[j]:
            break
    if i > 0:
        if a_ls[i-1] == a_ls[i]:
            not_divisible = False
    if i < n-1:
        if a_ls[i+1] == a_ls[i]:
            not_divisible = False
    if not_divisible:
        ans += 1
print(ans)


### FIXED CODE ###

n = int(input())
a_ls = list(map(int, input().split()))
a_ls.sort()
a_max = a_ls[-1]
times_ls = [0] * (a_max + 1)
divisible_ls = [0] * (a_max + 1)
for i in range(n):
    base = a_ls[i]
    times_ls[base] += 1
    times = 2
    while base*times <= a_max:
        divisible_ls[base*times] = 1
        times += 1
ans = 0
for i in range(1,a_max+1):
    if times_ls[i] == 1 and divisible_ls[i] == 0:
        ans += 1
print(ans)
### BUGGY CODE ###

N = int(input())
A_list = list(map(int, input().split(' ')))
count_list = [A_list.count(i) for i in range(N+1)]

sum_ = 0
for count in count_list:
  sum_ += (count**2 - count) // 2

for i in range(N):
  num = count_list[A_list[i]]
  ans = sum_ - (num**2-num)//2 + (num**2-3*num+2)//2
  print(ans)

### FIXED CODE ###

import collections

N = int(input())
A_list = list(map(int, input().split(' ')))
count_dict = collections.Counter(A_list)

sum_ = 0
for count in count_dict.values():
  sum_ += (count**2 - count) // 2

for A in A_list:
  print(sum_ - count_dict[A] + 1)
### BUGGY CODE ###

import numpy as np
import math
N, K = map(int, input().split())
A = np.array(list(map(int, input().split())))

# 一度照らされると二度目以降は確実に照らされるはず。
for i in range(K):
    # j番目の電球を操作
    B = np.array([0] * N)
    if list(set(A)) == [N]:
        break
    for j in range(N):
        if A[j] == N:
            B[j] = N
            continue
        maxA = int(j + A[j] + 0.5)
        minA = math.ceil(j - A[j] - 0.5)

        for k in range(max(0, minA), min(N, maxA + 1)):
            B[k] += 1
    A = B.copy()

for i in range(N):
    if i != (N - 1):
        print(A[i], end=" ")
    else:
        print(A[i])


### FIXED CODE ###

import numpy as np
from numba import njit
N, K = map(int, input().split())
A = np.array(list(map(int, input().split())), dtype=np.int64)


@njit
def solve(N, K, A):
    # 一度照らされると二度目以降は確実に照らされるはず。
    for i in range(K):
        # j番目の電球を操作
        B = np.zeros(N + 1, dtype=np.int64)
        for j in range(N):
            # 左辺を確認
            B[max(j - A[j], 0)] += 1
            # 右辺を確認(なんで-1?)
            B[min(j + A[j] + 1, N)] -= 1

        A = np.cumsum(B)[:-1]

        if np.all(A == N):
            return A

    else:
        return A


A = solve(N, K, A)
for i in range(N):
    if i != (N - 1):
        print(A[i], end=" ")
    else:
        print(A[i])
### BUGGY CODE ###

#!/usr/bin/env python

import sys

n,m= [ int(x) for x in sys.stdin.readline().split() ]
baito=[ [] for _ in range(m) ]
for _ in range(n):
    ai,bi = [ int(x) for x in sys.stdin.readline().split() ]
    ai-=1
    if ai<m: baito[ai].append(bi)
#
tot=0
cur=[]
for i in range(m):
    ref= baito[i]
    if ref:
        cur+= ref
        cur.sort()
    #
    if not cur: continue
    tot+= cur.pop()
#
print( tot )


### FIXED CODE ###

#!/usr/bin/env python

import sys

n,m= [ int(x) for x in sys.stdin.readline().split() ]
baito=[ [] for _ in range(m) ]
for _ in range(n):
    ai,bi = [ int(x) for x in sys.stdin.readline().split() ]
    ai-=1
    if ai<m: baito[ai].append(bi)
#
for i in range(m):
    if baito[i]: baito[i].sort()
#
tot=0
cur=[]
for i in range(m):
    ref= baito[i]
    if ref:
        if not cur:
            cur= ref
        else:
            if ref[-1]<=cur[0]:
                cur= ref + cur
            elif cur[-1]<=ref[0]:
                cur= cur + ref
            else:
                cur+= ref
                cur.sort()
    #
    if not cur: continue
    tot+= cur.pop()
#
print( tot )
### BUGGY CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))
 
dp = [100000000000]*N
 
dp[0] = 0
dp[1] = abs(h[1]-h[0])
 
for i in range(2,N):
  for num in range(min(K,i)):
      dp[i]=min(dp[i],dp[i-num-1]+abs(h[i]-h[i-num-1]))
 
print(dp[N-1])

### FIXED CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))
 
dp = [100000000000]*N
 
dp[0] = 0
dp[1] = abs(h[1]-h[0])
 
for i in range(2,N):
  for num in range(K):
    if num+1<=i:
      A = dp[i-num-1]+abs(h[i]-h[i-num-1])
      if dp[i] >= A:
        dp[i] = A
 
print(dp[N-1])
### BUGGY CODE ###

n = int(input())
s = input()
r = []
g = []
b = []
for i, x in enumerate(s):
  if x == 'R':
    r.append(i)
  elif x == 'G':
    g.append(i)
  else:
    b.append(i)
ans = 0
for i in r:
  for j in g:
    for k in b:
      if abs(i - j) != abs(j - k) and abs(j - k) != abs(k - i) and abs(k - i) != abs(i - j):
        ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
ans = s.count('R') * s.count('G') * s.count('B')
for i in range(n - 2):
  for j in range(1, (n - i + 1) // 2):
    if s[i] != s[i+j] and s[i+j] != s[i+j*2] and s[i+j*2] != s[i]:
      ans -= 1
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sun Apr 26 16:50:16 2020

@author: hiroki
"""


N = int(input())
A = list(map(int, input().split()))
sub = []

for i in range(N):
    sub.append(A.count(i+1))

for i in range(len(sub)):
    print(sub[i])



### FIXED CODE ###

import numpy as np

N = int(input())
A = np.array(list(map(int, input().split())))

sub = np.bincount(A, weights=None, minlength=N+1)

for i in range(N):
    print(sub[i+1])
### BUGGY CODE ###

import numpy as np
N=int(input()) 
A=list(map(int,input().split()))
count=0
allcount=0
matrix=[]
ans=[0]*N
for i in range(N):
    buf=[0]*N
    if i==N-1:
        buf[0]=1
        buf[N-1]=1
    else:
        buf[i]=1
        buf[i+1]=1
    matrix.append(buf)
matrix=np.matrix(matrix)
A=np.array(A)
A=np.reshape(A,(1,N))
right=A.T
#print(right)
#print(matrix)
#print(np.linalg.inv(matrix))
rev=np.linalg.inv(matrix)
B=rev*right
#print(B)
B=np.reshape(B,(1,N))
B=B.tolist()
#print(B)
for i in range(N):
    ans[i]=int(2*B[0][i])
print(*ans,sep=" ")

### FIXED CODE ###

#N%2==1なので
#a1=S-2((a2+a3)+(a4+a5)+...+(aN-1+aN))
#=S-2(A2+A4+...+AN-1)よりa1を求め
#ai+ai+1=2Ai<=>ai+1=2Ai-aiより再帰的にa2以降を求める
N=int(input())
A=list(map(int,input().split()))
count=0
allcount=0
matrix=[]
ans=[0]*N
allsum=0
a1=0
for i in range(N):
    allsum=allsum+A[i]
a1=allsum
for i in range(N):
    if i%2==1:
        a1=a1-2*A[i]
ans[0]=a1
for i in range(0,N-1,1):
    ans[i+1]=2*A[i]-ans[i]
print(*ans,sep=" ")
### BUGGY CODE ###

import math
import random as rd
import numpy as np

a,b,c,n=map(int,input().split( ))

s=0
for i in range(n//a+1):
    for j in range(n//b+1):
        ck=(n-a*i-b*j)
        if ck%c==0 and ck//c>=0:
            s+=1
        # print(i,j,ck,s)

print(s)



### FIXED CODE ###

a,b,c,n=map(int,input().split( ))

s=0
for i in range(n//a+1):
    for j in range((n-a*i)//b+1):
        ck=(n-a*i-b*j)
        if ck%c==0 and ck//c>=0:
            s+=1
        # print(i,j,ck,s)

print(s)
### BUGGY CODE ###

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

N_man_max = Y // 10000
N_gos_max = Y // 5000
N_sen_max = Y // 1000
flag = False
for i in range(N_man_max +1):
    if flag == True:
        break
    for j in range(N_gos_max +1):
        for k in range(N_sen_max +1):
            if 10000*i + 5000*j + 1000*k == Y and i+j+k == N:
                print(i,j,k)
                flag = True
if flag == False:
    print(-1, -1, -1)

### FIXED CODE ###

N, Y = map(int, input().split())
flag = False

for x in range(N+1):
    if flag == True:
        break
    for y in range(N-x+1):
        if 10000*x + 5000*y + 1000*(N-x-y) == Y:
            print(x, y, N-x-y)
            flag = True
            break

if flag == False:
    print(-1, -1, -1)
### BUGGY CODE ###

n=int(input())

a=[]


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


c=int(a[0])

for k in range(1,n):

    c*=int(a[k])

if c>10**18:
    print(-1)

else:
    print(c)


### FIXED CODE ###

n=int(input())

a=[]

import sys

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


c=1
if a.count(0)>=1:
    print(0)
    sys.exit()

for k in range(n):

    c*=int(a[k])

    if c>10**18:
        print(-1)
        sys.exit()


print(c)
### BUGGY CODE ###

a, b = map(int, input().split())
c = 1
for i in range(a, b+1):
    c *= i
if c==0:
    print("Zero")
elif c>0:
    print("Positive")
else:
    print("Negative")

### FIXED CODE ###

a, b = map(int, input().split())
if a>0 and b>0:
    print("Positive")
elif a==0 or b==0:
    print("Zero")
elif (a>0 and b<0) or (a<0 and b>0):
    print("Zero")
elif ((a+b)+1)%2==0:
    print("Positive")
else:
    print("Negative")
### BUGGY CODE ###

N = int(input())
A = [int(k) for k in input().split(' ')]

from collections import Counter 
import math 

# res = [] # solution for each key in A
res_list = {} # solution for each value in A

# counter ver
A_c = Counter(A)
l = len(A_c)

def ncr(j):
  return math.factorial(j) // math.factorial(2) // math.factorial(j - 2) if j >= 2 else 0

# store ncr for each value 
combs = {k: ncr(v) for k, v in A_c.items()}

s = sum(combs.values())
  
for m in A_c.keys():
  cnt = combs[m]

  n = s
  n -= cnt # the only inaccurate entry
  n += ncr(A_c[m] - 1)
  res_list[m] = n

res = []
# for k in range(N):
#   res += '\n' + str(res_list[A[k]])
# print(res[1:])
for k in range(N):
  res.append(res_list[A[k]])
print('\n'.join([str(s) for s in res]))

### FIXED CODE ###

N = int(input())
A = [int(k) for k in input().split(' ')]

from collections import Counter 
import math 

res = [] # solution for each key in A
res_list = {} # solution for each value in A

# counter ver
A_c = Counter(A)
l = len(A_c)

def ncr(j):
  return int(j * (j-1) / 2) if j >= 2 else 0

# store ncr for each value 
combs = {k: ncr(v) for k, v in A_c.items()}

s = sum(combs.values())
  
for m in A_c.keys():
  res_list[m] = s - combs[m] + ncr(A_c[m] - 1)

for k in range(N):
  res.append(res_list[A[k]])
print('\n'.join([str(s) for s in res]))
### BUGGY CODE ###

N = int(input())

Alist = [int(input()) for i in range(N)]

for i in range(N):
    print(max(Alist[:i]+Alist[i+1:]))


### FIXED CODE ###

N = int(input())

Alist = [int(input()) for i in range(N)]

Blist = sorted(Alist, reverse=True)

for i in range(N):
    if Alist[i] == Blist[0]:
        print(Blist[1])
    else:
        print(Blist[0])
### BUGGY CODE ###

def grundy(N, K):
    while N % K:
        m = N / K + 1
        N -= m
    return N / K

N = input()
ans = 0
for i in xrange(N):
    a, k = map(int, raw_input().split())
    ans ^= grundy(a, k)
print "Takahashi" if ans else "Aoki"

### FIXED CODE ###

def grundy(N, K):
    if N < K:
        return 0
    while N % K:
        hi = N / (N / K + 1) 
        lo = 1
        while hi - lo > 1:
            mid = (hi + lo) / 2
            M = N - mid * (N/ K + 1)
            if M / K == N / K:
                lo = mid
            else:
                hi = mid
        m = N / K + 1
        N -= m * lo
    return N / K

N = input()
ans = 0
for i in xrange(N):
    a, k = map(int, raw_input().split())
    ans ^= grundy(a, k)
print "Takahashi" if ans else "Aoki"
### BUGGY CODE ###

n, q = map(int, input().split())
edges = [set() for i in range(n)]
for _ in range(n-1):
    a, b= map(int,input().split())
    edges[a-1].add(b-1)
cnt = [0] * n

for _ in range(q):
    p, x = map(int, input().split())
    l = [p-1]
    while len(l) != 0:
        a = l.pop()
        cnt[a] += x
        for i in edges[a]:
            l.append(i)
print(*cnt)


### FIXED CODE ###

n, q = map(int, input().split())
# tree = [list(map(int, input().split())) for i in range(n-1)]
edges = [set() for i in range(n)]
for _ in range(n-1):
    a, b= map(int,input().split())
    edges[a-1].add(b-1)
cnt = [0] * n

for _ in range(q):
    p, x = map(int, input().split())
    cnt[p-1] += x

l = [0]
l2 = [cnt[0]]
while len(l) != 0:
    a = l.pop()
    b = l2.pop()
    if a != 0:
        cnt[a] += b
    for i in edges[a]:
        l.append(i)
        l2.append(cnt[a])
print(*cnt)
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
AB = sorted((a + b for a in A for b in B), reverse=True)[:min(X*Y, K)]
C.sort()
ABC = sorted((ab + c for ab in AB for c in C), reverse=True)[:K]
print('\n'.join(map(str, ABC)))


### FIXED CODE ###

from heapq import heappush, heappop

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
AB = sorted((a + b for a in A for b in B), reverse=True)[:min(X*Y, K)]
C.sort()

heap = []
min_sum = float('inf')
for ab in AB:
    if len(heap) < K:
        for c in C:
            heappush(heap, -(ab + c))
            min_sum = min(min_sum, ab + c)
    else:
        left = 0
        right = Z
        while left < right:
            mid = (left+right) // 2
            n = ab + C[mid]
            if n >= min_sum:
                left = mid + 1
            else:
                right = mid
            min_sum = min(min_sum, n)
        for c in C[:right]:
            heappush(heap, -(ab + c))


for i in range(K):
    print(-heappop(heap))
### BUGGY CODE ###

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

## make 'next_lst'
## S='1100010000' --> next_lst=[2,3,1,4,1]
next_lst = []
pre_state = S[0]
cnt = 1
for i in range(1,len(S)):
  if S[i] == pre_state:
    cnt += 1
  else:
    next_lst.append(cnt)
    pre_state = S[i]
    cnt = 1
else:
  next_lst.append(cnt)
if S[0] == '0':
  next_lst = [0] + next_lst
if S[-1] == '0':
  next_lst = next_lst + [0]
#print(next_lst)

ans = 0
if len(next_lst) <= 2*K+1:
  ans = sum(next_lst)
  print(ans)
  exit()
for i in range((len(next_lst)-2*K+1)//2):
  var = sum(next_lst[2*i:2*i+(2*K+1)])
  ans = max(ans, var)
  #print(i, var, next_lst[2*i:2*i+(2*K+1)])
  
print(ans)
  

### FIXED CODE ###

import numpy as np

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

## pesmistic input (8916 ms)
#N = 100000
#K = 10000
#S = '10'*50000

## make 'next_lst'
## S='1100010000' --> next_lst=[2,3,1,4,1]
next_lst = []
pre_state = S[0]
cnt = 1
for i in range(1,len(S)):
  if S[i] == pre_state:
    cnt += 1
  else:
    next_lst.append(cnt)
    pre_state = S[i]
    cnt = 1
else:
  next_lst.append(cnt)
if S[0] == '0':
  next_lst = [0] + next_lst
if S[-1] == '0':
  next_lst = next_lst + [0]


if len(next_lst) <= 2*K+1:
  ans = sum(next_lst)
  print(ans)
  exit()

## 配列の区間和はcumsumで累積和を取ってその差分を取るほうが速い
ans = 0
lst = np.cumsum(np.array([0]+next_lst))
for i in range((len(next_lst)-2*K+1)//2):
  var = lst[2*i+2*K+1] - lst[2*i]
  ans = max(ans, var)

print(ans)