Harryxun/stf_run huggingface dataset:
from collections import deque
import numpy as np

N, Q = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N-1)]
P = [list(map(int, input().split())) for _ in range(Q)]

dist = [-1 for _ in range(N)]
ans = [0 for _ in range(N)]
parent = [[] for _ in range(N)]
dist[0] = 0
d = deque([0])
while d:
    now = d.popleft()
    for i in range(N-1):
        if A[i][0] - 1 == now and dist[A[i][1] - 1] == -1:
            dist[A[i][1] - 1] = now + 1
            d.append(A[i][1] - 1)
            parent[A[i][1] - 1].append(dist[A[i][0] - 1])

        if A[i][1] - 1 == now and dist[A[i][0] - 1] == -1:
            dist[A[i][0] - 1] = now + 1
            d.append(A[i][0] - 1)
            parent[A[i][0] - 1].append(dist[A[i][1] - 1])

arg_dist = np.argsort(np.array(dist))

for i in range(Q):
    ans[P[i][0] - 1] += P[i][1]

for i in range(N):
    for j in range(len(parent[arg_dist[i]])):
        ans[arg_dist[i]] = ans[arg_dist[i]] + ans[parent[arg_dist[i]][j]]

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


### FIXED CODE ###

from collections import deque
import numpy as np

N, Q = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N-1)]
P = [list(map(int, input().split())) for _ in range(Q)]

link = [[] for _ in range(N)]
for i in range(N-1):
    link[A[i][0]-1].append(A[i][1]-1)
    link[A[i][1]-1].append(A[i][0]-1)


ans = [0 for _ in range(N)]
for i in range(Q):
  ans[P[i][0] - 1] += P[i][1]

dist = [-1 for _ in range(N)]
dist[0] = 0
d = deque([0])
while d:
    now = d.pop()
    for i in range(len(link[now])):
        if dist[link[now][i]] == -1:
            ans[link[now][i]] += ans[now]
            dist[link[now][i]] = 0
            d.append(link[now][i])

for i in range(N):
    if i != N - 1:
        print(ans[i], end=" ")
    else:
        print(ans[i])
n = int(input())
a = [int(_) for _ in input().split()]

sub_num = [0]*(2*10**6)

for i in range(1, n+1):
#    print(abs(int(a[i-1]-i)))
    sub_num[abs(int(a[i-1]-i))] += 1

b = -sub_num.index(max(sub_num))
#print(b)

result = 0
for i in range(1, n+1):
    result += abs(a[i-1] - (b + i))

print(result)

### FIXED CODE ###

n = int(input())

if(n % 2 == 0):
    print(n)
else:
    print(n*2)
N,M = map(int,input().split())
H = list(map(int,input().split()))
XX = [set() for i in range(N)]
ans = 0
for i in range(M):
  A,B = map(int,input().split())
  XX[A-1].add(B)
  XX[B-1].add(A)
  
for i in range(N):
  for y in XX[i]:
    r = True
    if H[i]<=H[y]:
      r = False
      break
    if r:
      ans += 1

print(ans)


### FIXED CODE ###

N,M = map(int,input().split())
H = list(map(int,input().split()))
AB = [set() for i in range(N)]
for i in range(M):
    A,B = map(int,input().split())
    AB[A-1].add(B-1)
    AB[B-1].add(A-1)
ans = 0
for i in range(N):
    res = True
    for x in AB[i]:
        if H[i]<=H[x]:
            res = False
            break
    if res:
        ans += 1
print(ans)
N, M = map(int, input().split())
L = []
R = []
D = []
for i in range(M):
    l, r, d = map(int, input().split())
    L.append(l)
    R.append(r)
    D.append(d)

inf = float("inf")


class WDG():  # 重み付き有向グラフ(隣接リスト表現)
    class node():
        def __init__(self, index=0, weight=0, next=None):
            self.index = index
            self.weight = weight
            self.next = next

    def __init__(self, N, M, L, R, D):
        self.heads = []
        self.x = [None] * N
        self.N = N
        self.M = M
        for i in range(N):
            head = WDG.node()
            head.next = head
            head.index = i
            self.heads.append(head)
        for i in range(M):
            new1 = WDG.node(R[i] - 1, D[i], head)
            new2 = WDG.node(L[i] - 1, -D[i], head)
            self.insert(L[i] - 1, new1)
            self.insert(R[i] - 1, new2)

    def insert(self, start, new):
        new.next = self.heads[start].next
        self.heads[start].next = new

    def show_graph(self):
        for i in self.heads:
            node = i.next
            print("{}=>".format(i.index + 1), end="")
            while node != i:
                print("{}({})".format(node.index + 1, node.weight), end=" ")
                node = node.next
            print("")

    def _DFS(self, s_head):  # 始点sから到達できる連結成分を深さ優先探索
        node = s_head.next
        while node != s_head:
            new_x = self.x[s_head.index] + node.weight
            if self.x[node.index] is not None and self.x[node.index] != new_x:
                return False
            elif self.x[node.index] == new_x:
                pass
            else:
                #print("node{}".format(node.index + 1))
                self.x[node.index] = new_x
                self._DFS(self.heads[node.index])
            node = node.next
        return True

    def DFS(self):  # すべての点を訪れるまで深さ優先探索
        for i in range(self.N):
            #print("{}個目の連結成分".format(i + 1))
            node = self.heads[i]
            if self.x[node.index] is None:
                self.x[node.index] = 0
                if not self._DFS(self.heads[node.index]):
                    return "No"
        return "Yes"


G = WDG(N, M, L, R, D)
# G.show_graph()
print(G.DFS())


### FIXED CODE ###

from collections import deque
N, M = map(int, input().split())
G = [[] for _ in range(N)]
for i in range(M):
    l, r, d = map(int, input().split())
    G[l - 1].append((r - 1, d))
    G[r - 1].append((l - 1, -d))
q = deque()

x = [None] * N


def _BFS(start):
    q.append(start)
    while len(q) != 0:
        p = q.popleft()
        for index, d in G[p]:
            if x[index] is None:
                x[index] = x[p] + d
                q.append(index)
            elif x[index] != x[p] + d:
                return False
    return True


def BFS():
    for i in range(N):
        if x[i] is None:
            x[i] = 0
            if not _BFS(i):
                return "No"
    return "Yes"


print(BFS())
a, b, c= map(int, input().split())
print( sum(a, b, c) - max(a, b, c))

### FIXED CODE ###

p, q, r = map(int, input().split())
print(p + q+ r - max(p, q, r))
a, b = list(map(int, input()))
if a > 9 or b > 9:
  print(-1)
else:
  print(a * b)

### FIXED CODE ###

a, b = list(map(int, input().split(" ")))
if a > 9 or b > 9:
  print(-1)
else:
  print(a * b)
print("Yes" if int(input())>="30" else "No")

### FIXED CODE ###

print("Yes" if int(input())>=30 else "No")
a,b,c,x,y = map(int,input().splir())
cnt = 0
if 2*c < a+b:
    cnt += abs(x-y)*c*2
    if x > y:
        c += (x-y)*a
    else:
        c += (y-x)*b
else:
    cnt += a*x + b*y
print(cnt)

### FIXED CODE ###

a,b,c,x,y = map(int,input().split())
cnt = 0
if 2*c < a+b:
    cnt += min(x,y)*c*2
    if x >= y:
        cnt += min((x-y)*a,(x-y)*2*c)
    else:
        cnt += min((y-x)*b,(y-x)*2*c)
else:
    cnt += a*x + b*y
print(cnt)
N = input()
ABCDE = []
for i in range(4):
    A = input()
    ABCDE.append(A)
m = min(ABCDE)
if N % m == 0:
    print(N // m)
else:
    print(N // m + 1)

### FIXED CODE ###

N = int(input())
A = int(input())
B = int(input())
C = int(input())
D = int(input())
E = int(input())
m = min(A, B, C, D, E)
if N % m == 0:
    print(N // m + 4)
else:
    print(N // m + 5)
S =[]
T =[]
i = random.choice(S,C,R)
 S[0] ='i'
i = random.choice(S,C,R)
S[1] ='i'
i = random.choice(S,C,R)
S[2] ='i'

i = random.choice(S,C,R) 
T[0] ='i'
i = random.choice(S,C,R)
T[1] ='i'
i = random.choice(S,C,R)
T[2] ='i'
 
if S[0]=T[0]:
  correct += 1
  if S[1]=T[1]:
    correct += 1
    if S[2]=S[2]:
      correct += 1
 
print(correct)

### FIXED CODE ###

S=input()
T=input()

ans=0
for s,t in zip(S,T):
  if s==t:
    ans+=1
print(ans)
from math import *
while True:
    n = int(input())
    if n == 0:
        break
    for i in range(n):
        sco = map(int,raw_input().split())
        ave=0.0
        for i in sco:
            ave += i
        ave /= n

        dev = 0.0
        for i in sco:
            dev += (i-ave)*(i-ave)
        dev /= n

        print sqrt(dev)

### FIXED CODE ###

from math import *
while True:
    n = 0
    n = int(input())
    if n == 0:
        break
    else :
        sco = map(int,raw_input().split())
        for i in range(n):
            ave=0.0
            for i in sco:
                ave += i
            ave /= n
            dev = 0.0
            for i in sco:
                dev += (i-ave)*(i-ave)
            dev /= n
        print sqrt(dev)
def dfs(v,d):
    k_shortest[v] = d
    visit[v] = 1
    for i,j in tree[v]:
        if not visit[i]:
            dfs(i,d+j)

N=int(input())
tree=[[] for i in range(N+1)]
visit = [0]*(N+1)
k_shortest = [0]*(N+1)
for i in range(N-1):
    a,b,c=map(int,input().split(' '))
    tree[a].append((b,c))
    tree[b].append((a,c))
Q,K=map(int,input().split(' '))
dfs(K,0)
query = [list(map(int,input().split(' '))) for i in range(Q)]
for i,j in query:
    print(k_shortest[i]+k_shortest[j])


### FIXED CODE ###

from collections import deque

N = int(input())
ABC=[map(int,input().split(' ')) for i in range(N-1)]
Q,K =  map(int,input().split(' '))
query = [map(int,input().split(' ')) for i in range(Q)]
tree = [[] for i in range(N+1)]
for a,b,c in ABC:
    tree[b].append((a,c))
    tree[a].append((b,c))
k_shortest = [0]*(N+1)
stack=deque([K])
while stack:
    k = stack.popleft()
    for v,d in tree[k]:
        if k_shortest[v] == 0:
            k_shortest[v] = k_shortest[k]+d
            stack.append(v)
for i,j in query:
    print(k_shortest[i]+k_shortest[j])
n=int(input())
t,a=map(int,input().split())
lis=list(map(int,input().split()))
li,l=abs((t-lis[0]*0.006)-a),0
for i in range(1,n):
    b = abs((t-lis[i]*0.006)-a)
    if b < li:
        li=b
        l=i
print(l+1)

### FIXED CODE ###

a,b = map(int,input().split())
print(a+int(b/2))
x = int(input())
dp = [0]*x*100
dp[0] = 1
for i in range(x):
  if dp[i] == 1:
    dp[i + 100] =1
    dp[i + 101] =1
    dp[i + 102] =1
    dp[i + 103] =1
    dp[i + 104] =1
    dp[i + 105] =1
if dp[x] ==1:
  print(1)
else :
  print(0)

  
      
  
      

### FIXED CODE ###

x = int(input())
dp = [0]*(x + 106)
dp[0] = 1
for i in range(x):
  if dp[i] == 1:
    dp[i + 100] =1
    dp[i + 101] =1
    dp[i + 102] =1
    dp[i + 103] =1
    dp[i + 104] =1
    dp[i + 105] =1
if dp[x] ==1:
  print(1)
else :
  print(0)
N = int(input())
A = list(map(int,input().split()))

AB = sorted(A)
C = int(N/2)
for i in range(N):
    if AB[i] <= AB[C]:
        print(AB[C+1])
    else:
        print(AB[C])

### FIXED CODE ###

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

AB = sorted(A)
C = int(N//2)
for i in range(N):
    if A[i] <= AB[C-1]:
        print(AB[C])
    else:
        print(AB[C-1])
import sys

while 1:
  str = sys.stdin.readline().strip()
  a , b = sorted(str.split(" "), key=int)
  if a, b == "0":
    break
  print(a,b)

### FIXED CODE ###

import sys

while 1:
  a , b = sys.stdin.readline().split()
  if a == b == "0":
    break
  elif int(a) > int(b) :
    print(b,a)
  else :
    print(a,b)
import sys
N=int(input())
H=list(map(int,input().split()))
if N==1:
  print('Yes')
  sys.exit()
for i in range(N-1):
  if H[i]<H[i+1]:
    pass
  elif H[i]-H[i+1]==1:
    H[i]-=1
    if H[i+1]-H[i+2]>=1:
      print('No')
      sys.exit()
    else:
      pass
  elif H[i]-H[i+1]>=2:
    print('No')
    sys.exit()
print('Yes')

### FIXED CODE ###

import sys
N=int(input())
H=list(map(int,input().split()))
if N==1:
  print('Yes')
else:
  M=1
  for i in range(N-1):
    M=max(M,H[i])
    if H[i]<=H[i+1]:
      pass
    elif H[i]-H[i+1]==1:
      H[i]-=1
      if M-H[i]>1:
        print('No')
        sys.exit()
      else:
        pass
    elif H[i]-H[i+1]>=2:
      print('No')
      sys.exit()
  print('Yes')
N = input()
sum = 0
for n in N:
  sum += int(n)
res = int(N) % sum
if res == 0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

num = 0
s = input()
for op in s:
  if op == '+':
    num += 1
  else:
    num -= 1
print(num)
a=int(input())
b=int(input())
c=int(input())
d=int(input())
e=int(input())

dish = [a,b,c,d,e]
result=0

mx=-1

def dtime(a):
    for i in range(9):
        if a%10==0:
            return a
        else:
            a+=1

for dd in dish:
    for i in range(1,10):
        if (dd+i) % 10 == 0:
            tmp=i
            break
    if tmp > mx:
        mx = tmp
        buf=dd

dish.remove(buf)

for dd in dish:
    result+=dtime(dd)

print(result+buf)


### FIXED CODE ###

a=int(input())
b=int(input())
c=int(input())
d=int(input())
e=int(input())

dish = [a,b,c,d,e]
result=0

mx=-1

for dd in dish:
    for i in range(0,10):
        if (dd+i) % 10 == 0:
            tmp=i
            break
    if tmp > mx:
        mx = tmp
        buf=dd

dish.remove(buf)

for dd in dish:
    result+=dd
    for i in range(1,10):
        if result % 10 == 0:
            break
        result+=1
        
print(result+buf)
a = input()
b = input()

if(a > 8 || b > 8):
    print(':(')
else:
    print('Yay!')


### FIXED CODE ###

l = input().split()
a = int(l[0])
b = int(l[1])

if(a > 8 or b > 8):
    print (':(') 
else:
    print ('Yay!')
import math
from functools import reduce
N, X = map(int, input().split())
x = list(map(int, input().split()))
x.append(X)
x = sorted(x)
y = []
for i in range(len(x)-1):
    y.append(x[i+1]-x[i])
print(reduce(math.gcd, y))


### FIXED CODE ###

from functools import reduce


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

N, X = map(int, input().split())
x = list(map(int, input().split()))
x.append(X)
x = sorted(x)
y = []
for i in range(len(x)-1):
    y.append(x[i+1]-x[i])
print(reduce(gcd, y))
from collections import deque

h,w = map(int,input().split())
maze = []

for _ in range(h):
    maze.append(input())

ans = 0

move = [[1,0],[-1,0],[0,1],[0,-1]]

for i in range(h):
    for j in range(w):
        if(maze[i][j]=="."):
            dist = [ [99999999]*w for _ in range[i] ]
            
            dq = deque()
            y=i
            x=j
            d=0
            
            dq.append((y,x,d))
            
            while(len(dq)):
                
                y,x,d = dq.popleft()
                dist[y][x]=d
                for m in move:
                    if((0<=x+m[0]<w) and (0<=y+m[1]<h) and
                        (dist[y+m[1]][x+m[0]] > d+1) and
                            (maze[y+m[1]][x+m[0]] == ".")):
                                dq.append((y+m[1],x+m[0],d+1))
                                
            ans = max(ans,d)
            # print(d,i,j)
print(ans)

### FIXED CODE ###

from collections import deque

h,w = map(int,input().split())
maze = []

for _ in range(h):
    maze.append(input())

ans = 0

move = [[1,0],[-1,0],[0,1],[0,-1]]

for i in range(h):
    for j in range(w):
        if(maze[i][j]=="."):
            dist = [ [99999999]*w for _ in range(h) ]
            
            dq = deque()
            y=i
            x=j
            d=0
            dist[y][x]=0
            dq.append((y,x,d))
            
            while(len(dq)):
                
                y,x,d = dq.popleft()
                
                for m in move:
                    if((0<=x+m[0]<w) and (0<=y+m[1]<h) and
                        (dist[y+m[1]][x+m[0]] > d+1) and
                            (maze[y+m[1]][x+m[0]] == ".")):
                                dist[y+m[1]][x+m[0]]=d+1
                                dq.append((y+m[1],x+m[0],d+1))
                                
            ans = max(ans,d)
            # print(d,i,j)
print(ans)
A, B, C = map(int, input().split())
   
  if(A<C and C<B) or (B<C and C<A):
      print('Yes')
  else:
      print('No')   

### FIXED CODE ###

A, B, C = map(int, input().split())

if(A<C and C<B) or (B<C and C<A):
    print('Yes')
else:
    print('No')
import math
a = int(raw_input())
print a*2*math.pi,a*a*math.pi

### FIXED CODE ###

import math
a = float(raw_input())
print "{0:.6f} {1:.6f}".format(a*a*math.pi,a*2*math.pi)
S = str(input())
T = str(input())
tempcount = 0
mincount = 0

if S in T:
    print("0")
    exit

for i in range(len(S) - len(T)+1):
    for j in range(len(T)+1):
        if S[i + j] != T[j]:
            tempcount += 1
    if i == 0:
        mincount = tempcount
    elif tempcount < mincount:
        mincount = tempcount
    tempcount = 0
    
print(mincount)



### FIXED CODE ###

S = str(input())
T = str(input())
tempcount = 0
mincount = 0

for i in range(len(S) - len(T)+1):
    for j in range(len(T)):
        if S[i + j] != T[j]:
            tempcount += 1
    if i == 0:
        mincount = tempcount
    elif tempcount < mincount:
        mincount = tempcount
    tempcount = 0
    
print(mincount)
import itertools
s,ans=range(0,10),0
chk=list(itertools.combinations_with_replacement(s,4))
for j in sys.stdin:
    for k in chk:
        if sum(k)==int(j):
            ans+=1
    print ans

### FIXED CODE ###

import itertools
import sys
s=range(0,10)
chk=list(itertools.product(s,repeat=4))
for j in sys.stdin:
    ans=0
    for k in chk:
        if sum(k)==int(j):
            ans+=1
    print ans
num = int(input())
wr = str(input())

i_counts = []
r_num = wr.count("R")

for i in range(r_num):
  w_counts = 0
  r_counts = 0
  for j in range(num):
    if i > j and wr[j] == "W":
      w_counts += 1
    elif i < j and wr[j] == "R":
      r_counts += 1
  i_count = max(w_counts, r_counts)
  i_counts.append(i_count)

ans = min(i_counts)
print(ans)

### FIXED CODE ###

num = int(input())
wr = str(input())

r_num = wr.count("R")
i_counts = [r_num]
rw_count = r_num
wr_count = 0
for i in range(num):
  if wr[i] == "W":
    wr_count += 1
  else:
    rw_count -= 1
  i_count = max(wr_count, rw_count)
  i_counts.append(i_count)

ans = min(i_counts)

print(ans)
l = raw_input().split()
s = l[0] * l[1]
y = (l[0] + l[1]) * 2
print s

### FIXED CODE ###

l = map(int, raw_input().split())
print l[0] * l[1], 2 * (l[0] + l[1])
#from scipy.misc import comb
from scipy.special import comb
import itertools

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

combi = list(itertools.combinations(range(1,N+1), 2))
#print(combi)
dist = {}
for i in range(1, N):
    dist[i] = 0

for kyori in combi:
    if kyori[1] >= Y and kyori[0] <= X:
        c = (kyori[1] - Y) + 1 + (X - kyori[0])
    elif kyori[1] >= Y:
        a = kyori[1] - kyori[0]
        b = (kyori[1] - Y) + 1 + int(abs((X - kyori[0])))
        c = min([a, b])
    elif kyori[0] <= X:
        a = kyori[1] - kyori[0]
        b = int(abs(kyori[1] - Y)) + 1 + (X - kyori[0])
        c = min([a, b])
    else:
        c = kyori[1] - kyori[0]
    dist[c] += 1
    #print(c, kyori)
dist2 = sorted(dist.items())
#print(dist, dist2)
for i in range(0, N-1):
    print(dist2[i][1])


### FIXED CODE ###

import itertools

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

combi = list(itertools.combinations(range(1,N+1), 2))
dist = [[i+1, 0] for i in range(0, N-1)]

c = [min([kyori[1] - kyori[0], int(abs((kyori[1] - Y))) + 1 + int(abs((X - kyori[0])))]) for kyori in combi]

for i in range(len(c)):
    dist[c[i]-1][1] += 1
for i in range(0, N-1):
    print(dist[i][1])
a, b, c, d, e, f = map(int, input().split())
sug, dif2 = 0, 100
s = {}
wat1, wat2 = 100*a, 100*b
cap1, cap2 = a*e, b*e
for i in range(1,f//wat1+1):
    for j in range(f//wat2+1):
        if (wat1+cap1)*i+(wat2+cap2)*j<=f:
            s[cap1*i+cap2*j] = wat1*i+wat2*j
if s == {}:
    dif1 = f - wat1
    for i in range(10):
        for j in range(10):
            if 0<=(f-wat1) - (c*i+d*j)<dif1:
                dif1 = (f-wat1)-(c*i+d*j)
                sug3 = c*i+d*j
    print(wat1+sug3, sug3)
    exit(0)
print(wat,sug1, sug2)
for i in s.keys():
    for j in range(i//c+1):
        for k in range(i//d+1):
            if 0<=i-(c*j+d*k)<dif2:
                dif2 = i-(c*j+d*k)
                wat,sug1,sug2 = s[i],j,k
print(wat,sug1, sug2)
print(c*sug1+d*sug2+wat, c*sug1+d*sug2)

### FIXED CODE ###

a, b, c, d, e, f = map(int, input().split())
sug, dif2 = 0, 100
s = {}
wat1, wat2 = 100*a, 100*b
cap1, cap2 = a*e, b*e
for i in range(1,f//wat1+1):
    for j in range(f//wat2+1):
        if (wat1+cap1)*i+(wat2+cap2)*j<=f:
            s[cap1*i+cap2*j] = wat1*i+wat2*j
if s == {}:
    dif1 = f-wat1
    for i in range(10):
        for j in range(10):
            if 0<=(f-wat1)-(c*i+d*j)<dif1:
                dif1 = (f-wat1)-(c*i+d*j)
                sug3 = c*i+d*j
    print(wat1+sug3, sug3)
    exit(0)
for i in s.keys():
    for j in range(i//c+1):
        for k in range(i//d+1):
            if 0<=i-(c*j+d*k)<dif2:
                dif2 = i-(c*j+d*k)
                wat,sug1,sug2 = s[i],j,k
print(c*sug1+d*sug2+wat, c*sug1+d*sug2)
D=int(input())
s="Christmas"
e=" Eve"
if D==25:
  print(s)
  exit()
s+=e
if D==24:
  print(s)
  exit()
s+=e
if D==23:
  print(s)
  exit()
if D==22:
  priint(s+e)

### FIXED CODE ###

D=int(input())
s="Christmas"
e=" Eve"
if D==25:
  print(s)
  exit()
s+=e
if D==24:
  print(s)
  exit()
s+=e
if D==23:
  print(s)
  exit()
if D==22:
  print(s+e)
n, k = map(int, input().split())
s = list(map(lambda x: x == "1", list(input())))

change_flg = False
cnt = 0
ilands = []


def cumsum(array):
    value = array[0]
    results = [value] * len(array)
    for index, elm in enumerate(array[1:], 1):
        value += elm
        results[index] = value
    return results


def change():
    global cnt, change_flg
    ilands.append(cnt)
    cnt = 0
    change_flg = not change_flg

for value in s:
    if value: # case 1 cnt
        if change_flg:
            change()
    else: # case 0 cnt : plus
        if not change_flg:
            change()
    cnt += 1

ilands.append(cnt)

ilands += [0] * 10**5

if not len(ilands) % 2:
    ilands.append(0)

merged = list(cumsum(ilands))
section = 2 * k + 1

results = [0] * (len(ilands) // 2 - (k - 1))

merged.append(0)
for i in range(len(results)):
    start = i * 2 - 1
    results[i] = merged[start + section] - merged[start]

print(max(results))


### FIXED CODE ###

n, k = map(int, input().split())
s = list(map(lambda x: x == "1", list(input())))

change_flg = False
cnt = 0
ilands = []


def cumsum(array):
    value = array[0]
    results = [value] * len(array)
    for index, elm in enumerate(array[1:], 1):
        value += elm
        results[index] = value
    return results


def change():
    global cnt, change_flg
    ilands.append(cnt)
    cnt = 0
    change_flg = not change_flg

for value in s:
    if value: # case 1 cnt
        if change_flg:
            change()
    else: # case 0 cnt : plus
        if not change_flg:
            change()
    cnt += 1

ilands.append(cnt)

if not len(ilands) % 2:
    ilands.append(0)

merged = list(cumsum(ilands))
section = 2 * k + 1

results = [0] * (len(ilands) // 2 - (k - 1))
if len(results) < 1 or len(merged) < section:
    print(n)
    exit()

merged.append(0)
for i in range(len(results)):
    start = i * 2 - 1
    results[i] = merged[start + section] - merged[start]

print(max(results))
from sys import stdin,stdout
inp = stdin.readline
out = stdout.write
n = int(inp())
dp = [[0 for _ in range(3)] for _ in range(n)]
dp[0] = map(int,inp().split())
for i in range(1,n):
    a,b,c = map(int,inp().split())
    dp[i][0] = max(dp[i][1]+b[i],dp[i][2]+c[i])
    dp[i][1] = max(dp[i][0]+a[i],dp[i][2]+c[i])
    dp[i][2] = max(dp[i][1]+b[i],dp[i][0]+a[i])
out(str(max(dp[n-1])))

### FIXED CODE ###

from sys import stdin,stdout
inp = stdin.readline
out = stdout.write
n = int(inp())
dp = [[0 for _ in range(3)] for _ in range(n)]
dp[0] = list(map(int,inp().split()))
for i in range(1,n):
    a,b,c = map(int,inp().split())
    dp[i][0] = max(dp[i-1][1],dp[i-1][2])+a
    dp[i][1] = max(dp[i-1][0],dp[i-1][2])+b
    dp[i][2] = max(dp[i-1][1],dp[i-1][0])+c
out(str(max(dp[n-1])))
n,m = map(int,input().split())
l_n =list(list(map(int,input().split())) for i in range(n))
l_m =list(list(map(int,input().split())) for i in range(m))
q = 1000000
for i in range(n):
  q = 1000000
  for t in range(m):
    a,b = l_n[i]
    c,d = l_m[t]
    v= abs(a-c)+abs(b-d)
    if v<q:
      q = v
      z = t
  print(z+1)

### FIXED CODE ###

n,m = map(int,input().split())
l_n =list(list(map(int,input().split())) for i in range(n))
l_m =list(list(map(int,input().split())) for i in range(m))
for i in range(n):
  q = 10**9
  for t in range(m):
    a,b = l_n[i]
    c,d = l_m[t]
    v= abs(a-c)+abs(b-d)
    if v<q:
      q = v
      z = t
  print(z+1)