Harryxun/stf_run huggingface dataset:
N, K = [int(i) for i in input().split()]
S = input()
arr = []
val = 1
temp = S[0]
if temp == '1':
    arr += [0]
for s in S[1:]:
    if s == temp:
        val+=1
    else:
        arr += [val]
        val = 1
    temp = s
if val != 0:
    arr += [val]

print(max([sum(arr[i:i+K*2+1]) if i%2!=0 else sum(arr[i:i+K*2]) for i in range(len(arr)-(K*2)+1)]))


### FIXED CODE ###

N, K = [int(i) for i in input().split()]
S = input()
arr_0,arr_1 = [],[]
val = 1
temp = S[0]
if temp == '0':
    arr_1 += [0]
for s in S[1:]+"_":
    if s == temp:
        val+=1
    else:
        if temp=="1":
            arr_1 += [val]
        else:
            arr_0 += [val]
        val = 1
    temp = s
if S[-1] == "0":
    arr_1 += [0]

max_ = sum(arr_0[:K]+arr_1[:K+1])
for i in range(1, len(arr_0)-K+1):
    if (arr_0[i+K-1]+arr_1[i+K]) > (arr_0[i-1]+arr_1[i-1]):
        tmp = sum(arr_0[i:i+K])+sum(arr_1[i:i+K+1])
        if tmp > max_:
            max_ = tmp
print(max_)
D = int(input())
c = list(map(int,input().split()))
s = [list(map(int, input().split())) for l in range(D)]
last = [0]*26

def score_down(d):
    ans = 0
    for i in range(26):
        ans += c[i]*(d - last[i])
    return ans

for d in range(D):
    score = [(s[d][i] - score_down(d+1)) for i in range(D)]
    t = score.index(max(score))
    print(t+1)
    last[t] = d+1

### FIXED CODE ###

D = int(input())
c = list(map(int,input().split()))
s = [list(map(int, input().split())) for l in range(D)]
last = [0]*26

def score_down(d):
    ans = 0
    for i in range(26):
        ans += c[i]*(d - last[i])
    return ans

for d in range(D):
    score = [(s[d][i] - score_down(d+1)) for i in range(26)]
    t = score.index(max(score))
    print(t+1)
    last[t] = d+1
from scipy.special import comb

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

    A.sort()
    n = A[-1]
    maxc = 0
    for r in A[:-1]:
        cmb = comb(n, r)
        if maxc < cmb:
            ans = r
            maxc = cmb
    print(n, ans)

main()


### FIXED CODE ###

import bisect

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

    A.sort()
    n = A[-1]
    i = bisect.bisect_left(A, n / 2)
    if n / 2 - A[i-1] <= A[i] - n / 2:
        r = A[i-1]
    else:
        r = A[i]
    print(n, r)

main()
N = int(input())

for i in reversed(range(int(N**0.5))):
    j = int(N/i)
    if i*j == N:
        print(i-1+j-1)
        break

### FIXED CODE ###

N = int(input())

for i in reversed(range(1, int(N**0.5)+1)):
    j = int(N/i)
    if i*j == N:
        print(i-1+j-1)
        break
N = int(input())
H = input().split(" ")
height = 0
dp = [[0 for i in range(10`**4)] for n in range(N)]
def rec(n,h,cost):
  if n == N:
    return cost
  elif dp[n][h] != 0:
    return dp[n][h]
  else:
    dp[n][h] = min(rec(n+1,H[h+1],cost + abs(h-H[h+1])),rec(n+2,H[h+2],cost + abs(h-H[h+2])))
	return dp[n][h]
print(rec(0,H[0],0))

### FIXED CODE ###

N = int(input())
H = input().split(" ")
c = [10 ** 7 for i in range(N)]
c[0] = 0
c[1] = abs(int(H[0])-int(H[1]))
for i in range(N-2):
  c[i+2] = min(c[i]+abs(int(H[i])-int(H[i+2])),c[i+1]+abs(int(H[i+1])-int(H[i+2])))
print(c[len(c)-1])
a = int(input())
ans = a + a * a + a * a * a
print(ans)a = int(input())


### FIXED CODE ###

a = int(input())
ans = a + a * a + a * a * a
print(ans)
N = int(input())
A = list(map(int,input().split()))

A.sort()
flag = False
for count in range(0,len(A-1)):
    if A[count] == A[count+1]:
        flag = True
        break

if flag == False:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

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

A.sort()
flag = False
for count in range(0,len(A)-1):
    if A[count] == A[count+1]:
        flag = True
        break

if flag == False:
    print("YES")
else:
    print("NO")
n, m = map(int, input().split())

adj = [[] for i in range(n)]

for i in range(m):
    s, t = map(int, input().split())
    adj[s].append(t)
    adj[t].append(s)

isVisited = [False] * n

CC = [None] * n

import sys
sys.setrecursionlimit(10000)

def dfs(u, group):
    isVisited[u] = True
    CC[u] = group
    for v in adj[u]:
        if not isVisited[v]:
            dfs(v, group)

def makeCC(group):
    for i in range(n):
        if not isVisited[i]:
            dfs(i, group)
            group += 1

def isConnected(v1, v2):
    if CC[v1] == CC[v2]:
        print('yes')
    else:
        print('no')


makeCC(0)


q = int(input())

for i in range(q):
    s, t = map(int, input().split())
    isConnected(s, t)

### FIXED CODE ###

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

adj = [[] for i in range(n)]

for i in range(m):
    s, t = map(int, input().split())
    adj[s].append(t)
    adj[t].append(s)

groups = [None] * n


def dfs(u, group_num):
    path = []
    path.append(u)
    groups[u] = group_num
    while path:
        u = path[-1]
        if adj[u]:
            v = adj[u].pop(0)
            if not groups[v]:
                groups[v] = group_num
                path.append(v)
        else:
            path.pop()


g_n = 1
for i in range(n):
    if not groups[i]:
        dfs(i, g_n)
        g_n += 1

def isConnected(v1, v2):
    if groups[v1] == groups[v2]:
        print('yes')
    else:
        print('no')


q = int(input())

for i in range(q):
    s, t = map(int, input().split())
    isConnected(s, t)
import math
a,b,d = map(int,input().split())
c=0
for i in range(l,r+1):
  if i%d==0:
    c+=1
print(c)

### FIXED CODE ###

import math
a,b,d = map(int,input().split())
c=0
for i in range(a,b+1):
    if i%d==0:
        c+=1
print(c)
import collections


def main():
    s = list(input())
    if s.count("C") == 0 or s.count("F") == 0:
        print("No")
        return

    if s.index("C") == len(s) - 1:
        print("No")
        return

    print("Yes" if s.index("C") < s.index("F", s.index("C")) else "No")


if __name__ == '__main__':
    main()


### FIXED CODE ###

import collections


def main():
    s = list(input())
    if s.count("C") == 0 or s.count("F") == 0:
        print("No")
        return

    clen, flen = 0, 0
    for i in range(len(s)):
        if clen == 0:
            if s[i] == "C":
                clen = i
        if s[i] == "F":
            flen = i
    print("Yes" if flen > clen else "No")


if __name__ == '__main__':
    main()
inputs = list(map(int,input()))
a = inputs[1]
b = inputs[2]
c = inputs[3]

if a + b >= c and a <= c:
  print("YES")
else:
  print("NO")

### FIXED CODE ###

inputs = list(map(int,input().split(" ")))
a = inputs[0]
b = inputs[1]
c = inputs[2]
 
if a + b >= c and a <= c:
  print("YES")
else:
  print("NO")
a,b = [int(input().split()) for i in range(2)]
c = ( a * a )
d = (c - a)
print(d)

### FIXED CODE ###

m = int(input())
n = int(input())
m = m*m
print(m - n)
N,K = map(int,input().split())
h = list(map(int,input().split()))

dp = [0]*N
dp[1] = abs(h[1]-h[0])
for i in range(2,N):
  L = [dp[j] +abs(H[i] - H[j]) for j in range(max(0,i-K),i)]
  dp[i] = min(L)
print(dp[N-1])

### FIXED CODE ###

N,K = map(int,input().split())
H = [int(x) for x in input().split()]
 
def main(N,K,H):
    dp = [0]*N
    for i in range(1,N):
        L = [dp[j]+abs(H[i]-H[j]) for j in range(max(0,i-K),i)]
        dp[i] = min(L)
    print(dp[-1])
main(N,K,H)
n,q=map(int,input().split())
tree = [set() for _ in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    tree[a-1].add(b)
ans=[0]*n
def add_l(x):
    if not tree[x-1]:
        return
    for i in list(tree[x-1]):
        add_l(i)
        tree[x-1] |= tree[i-1]

add_l(1)
#print(tree)

for i in range(q):
    
    p,x=map(int,input().split())
    ans[p-1]+=x
    if tree[p-1]:

        for j in list(tree[p-1]):
            ans[j-1]+=x
print(*ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

# 遅延評価で加えてあげるだけ

N,Q = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

value = [0] * (N+1)
for p,x in PX:
    value[p] += x

def dfs(v,parent,add):
    value[v] += add
    for x in graph[v]:
        if x == parent:
            continue
        dfs(x,v,value[v])

dfs(1,0,0)

answer = ' '.join(map(str,value[1:]))
print(answer)
N = int(input())
S = input()
P = S.replace("B","")
if N%2 == 1:
  k = N//2+1
else:
  k = N//2
if len(P)>k:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

A,B,C = map(int,input().split())
if A == B == C:
    print("Yes")
else:
    print("No")
a, b, c = map(int, input().split())
max = int((a + c) / (b + 2*c))
print(max)

### FIXED CODE ###

X, Y = input().split()

if int(X, 16) > int(Y, 16):
    print(">")
elif int(X, 16) < int(Y, 16):
    print("<")
else:
    print("=")
m = int(input())


def a(x):
    k = 0
    while len(x) > 1:
        x = str(int(str(int(x[0]) + int(x[1])) + x[2:len(x)]))
        k += 1
    return x, k


k = 0
x = ""
for _ in range(m):
    d, c = [int(i) for i in input().split()]
    x += str(d) * c
    x, ka = a(x)
    k += ka
print(k)


### FIXED CODE ###

m = int(input())
a = 0
b = 0
for _ in range(m):
    d, c = [int(i) for i in input().split()]
    a += c
    b += d * c

print(a - 1 + (b - 1) // 9)
#ABC135A - Harmony
A, B = list(map(int,input().split()))
if (max(A,B) - min(A,B)) % 2 == 1:
    print("IMPOSSIBLE")
else:a
    print((A+B)//2)

### FIXED CODE ###

#ABC135A - Harmony
A, B = list(map(int,input().split()))
if (max(A,B) - min(A,B)) % 2 == 1:
    print("IMPOSSIBLE")
else:
    print((A+B)//2)
import sys
S = include()
a = "Sunny"
b = 'Cloudy'
c = 'Rainy'
if S == a:
    print(b)
elif S == b:
        print(c)
elif S == b:
        print(a)
else:
    sys.exit()
sys.exit()

### FIXED CODE ###

import sys
S = input()
a = "Sunny"
b = 'Cloudy'
c = 'Rainy'
if S == a:
    print(b)
elif S == b:
        print(c)
elif S == c:
        print(a)
else:
    sys.exit()
sys.exit()
import re

n = int(input())
v = sorted(list(map(int, input().split())))

ans = (v[0]+v[1])/2

if n == 2:
    ans = str(ans)

elif n > 2 and n % 2 == 0:
    for i in range(n/2):
        ans = str((ans + v[i+2])/2)

else:
    for i in range(n-2):
        ans = str((ans + v[i+2])/2)

if re.search('.0', ans):
   ans = ans.replace('.0', '')
   print(ans)

else:
    print(ans)

### FIXED CODE ###

n = int(input())
v = sorted(list(map(int, input().split())))

ans =v[0]

for i in range(n-1):
        ans = (ans + v[i+1])/2
print(ans)
in1 = input().split(' ')
N=int(in1[0])
M=int(in1[1])
K=int(in1[2])

inA = input().split(' ')
inB = input().split(' ')

T = 0
Ac=0
Bc=0

while T < K:
  
  if Ac>=N and Bc>=M:
    break
  elif Ac>=N:
    Bn=int(inB[Bc])
    T+=Bn
    Bc+=1
  elif Bc>=M:
    An=int(inA[Ac])
    T+=An
    Ac+=1
  else:
    An=int(inA[Ac])
    Bn=int(inB[Bc])
    if An>Bn:
      T+=An
      Ac+=1
    else:
      T+=Bn
      Bc+=1
  
  

print(Ac+Bc)

### FIXED CODE ###

a=int(input())

print(a+a*a+a*a*a)
number = int(imput())
odd_num = number // 2 + 1
percent = odd_num / number
print(percent)

### FIXED CODE ###

number = int(input())
if number % 2 == 0:
	odd_num = number // 2
	percent = odd_num / number
else:
	odd_num = number // 2 + 1
	percent = odd_num / number

print(percent)
def powmod(a, n, p):
    if(n==0):
        return 1
    elif(n==1):
        return a%p
    elif(n%2==1):
        return ((a%p)*(powmod(a,n//2,p)**2%p))%p
    elif(n%2==0):
        return powmod(a,n//2,p)**2%p
N=int(input())
if(N==1):
  print(0)
else:
  print(powmod(10,N-2))

### FIXED CODE ###

def powmod(a, n, p):
    if(n==0):
        return 2
    elif(n==1):
        return a%p
    elif(n%2==1):
        return ((a%p)*(powmod(a,n//2,p)**2%p))%p
    elif(n%2==0):
        return powmod(a,n//2,p)**2%p
N=int(input())
p=10**9+7
if(N==1):
    print(0)
else:
    print((powmod(10,N,p)-2*powmod(9,N,p)+powmod(8,N,p))%p)
import math

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

flag = False
gcd = math.gcd(n, m)
lcm = n * m // gcd
if s[0] == t[0]:
    if gcd == 1:
        flag = True
    else:
        if s[::lcm//len(t)] == t[::lcm//len(s)]:
            flag = True
if flag:
    print(lcm)
else:
    print(-1)

### FIXED CODE ###

import fractions

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

flag = False
gcd = fractions.gcd(n, m)
lcm = n * m // gcd
if s[0] == t[0]:
    if gcd == 1:
        flag = True
    else:
        if s[::lcm//len(t)] == t[::lcm//len(s)]:
            flag = True
if flag:
    print(lcm)
else:
    print(-1)
import math
N=int(input())
A=list(map(int,input().split(' ')))
ans = math.inf
l = []
for n,i in enumerate(A):
    l.append(i-n-1)
l = sorted(l)
for i in l[N//2-1:N//2+2]:
    tmp = 0
    for j in l:
        tmp += abs(j-i)
    ans = min(ans,tmp)
print(ans)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split(' ')))
ans = float('inf')
l = []
for n,i in enumerate(A):
    l.append(i-n-1)
l = sorted(l)
for i in l[N//2-1:N//2+2]:
    tmp = 0
    for j in l:
        tmp += abs(j-i)
    ans = min(ans,tmp)
print(ans)
S = int(input())

def seq(n):
    if n == 0:
        return 1
    elif n == 1 or n == 2:
        return 0
    else:
        return seq(n-1) + seq(n-3)

ans = seq(S)
mod = 10 ** 9 + 7
ans %= mod
print(ans)


### FIXED CODE ###

S = int(input())
mod = 10 ** 9 + 7

dp = [1, 0, 0]
cnt = 0
for i in range(3, S+1):
    cnt = dp[i-1] + dp[i-3]
    cnt %= mod
    dp.append(cnt)

ans = dp[S]
print(ans)
#!/usr/bin/env python
# -*- coding: utf-8 -*-

from collections import defaultdict
import itertools

def solve():
    t = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    dt = {0:0, 1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}

    n, m = map(int, input().split())
    al = [int(i) for i in input().split()]
    al.sort(reverse=True)
    d = defaultdict(list)
    for i in al:
        d[dt[i]].append(i)
    k = list(sorted(d.keys()))
    ans = ''
    if n % k[0] == 0:
        ans += str(d[k[0]][0]) * (n // k[0])
    else:
        p = n % k[0]
        s = []
        k1 = k[1:]
        for i in range(9, 0, -1):
            if i > len(k1):
                continue
            for j in list(itertools.combinations(k1, i)):
                l = [dt[w] for w in j]
                if p == sum(l) % k[0]:
                    s.append(list(j))
        mt, ma, mx = 10 ** 20, [0] * 5, 0
        tans = [None] * len(s)
        for idx, i in enumerate(s):
            i.sort(reverse=True)
            _tans = ''.join([str(d[w][0]) for w in i])
            _tans += str(d[k[0]][0]) * ((n - sum(i)) // k[0])
            _tans = list(_tans)
            _tans.sort(reverse=True)
            tans[idx] = (''.join(_tans))
        ans = 0
        for i in tans:
            ans = max(ans, int(i))
        ans = str(ans)
    ans = list(ans)
    ans.sort(reverse=True)
    print(''.join(ans))


if __name__=="__main__":
    solve()


### FIXED CODE ###

a, b = map(int, input().split())
print((a + b) if b % a == 0 else (b - a))
#! -*- coding:utf-8 -*-
O = str(input())
E = str(input())
O = list(O)
E = list(E)
n = 0
arr = []
for i in range(len(O)*2):
    if n % 2 == 0:
        arr.append(O.pop(0))
    else:
        arr.append(E.pop(0))
    n += 1
    
for i in range(len(arr)-1):
    print(arr[i],end = '')
print(arr[-1])


### FIXED CODE ###

#! -*- coding:utf-8 -*-
O = str(input())
E = str(input())
O = list(O)
E = list(E)
n = 0
arr = []
for i in range(len(O)*2):
    if n % 2 == 0:
        try:
            arr.append(O.pop(0))
        except:
            pass
    else:
        try:
            arr.append(E.pop(0))
        except:
            pass        
    n += 1
try:
    arr.append(O.pop(0))
except:
    pass

for i in range(len(arr)-1):
    print(arr[i],end = '')

print(arr[-1])
n,k=map(int,input('').split())
A=list(map(int,input('').split()))
prev=A[k-1]*A[0]
for i in range(k,n):
    j=i-k+1
    while(A[i]*A[j]==prev and j<n):
        j+=1
        prev=A[k-1]*A[j+k-1-i]
    if A[i]*A[j]>prev:
        print('Yes')
    else:
        print('No')
    prev=A[i]*A[i-k+1]


### FIXED CODE ###

n,k=map(int,input('').split())
A=list(map(int,input('').split()))
for i in range(k,n):
    if A[i]>A[i-k]:
        print('Yes')
    else:
        print('No')
n=input()

c=0
flag=0
for i in range(n):
  a,b = map(int(),input().split())
  if(a==b):
    c+=1
  else:
    c=0
  if(c==3):
    print("Yes")
    flag=1
    break
if(flag==0):
  print("No")

### FIXED CODE ###

n=int(input())

c=0
flag=0
for i in range(n):
  a,b = map(int,input().split())
  if(a==b):
    c+=1
  else:
    c=0
  if(c==3):
    print("Yes")
    flag=1
    break
if(flag==0):
  print("No")
#ABC126 B

S = list(map(int,input()))
if 1 <= S[0]*10 + S[1] <= 12 and 1 <= S[2]*10 + S[3] <= 12:
    print("AMBIGUOUS")
elif 1 <= S[0]*10 + S[1] <= 12 and (S[2]*10 + S[3] > 12 or S[2]*10 + S[3] == 0):
    print("MMYY")
elif (S[0]*10 + S[1] > 12 or S[0]*10 + S[1] == 0)  and  1 <= S[2]*10 + S[3] <= 12:
    print("YYMM")
elif (S[0]*10 + S[1] > 12 or S[0]*10 + S[1] == 0) and (S[2]*10 + S[3] > 12 or S[2]*10 + S[3] == 0):
    print("NA")

### FIXED CODE ###

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

for i in range(N):
    if i == K-1:
        T[i] = str.lower(T[i])

print("".join(T))
from collections import defaultdict as dd

N, M = map(int, input().split())
MOD = 10 ** 9 + 7
# a1 x a2 x .. x aN = M となる数列{ai}が何通りあるか
# まずは素因数分解
def make_prime_dict(x):
    primes = dd(int)
    check = 2
    while True:
        if x % check == 0:
            primes[check] += 1
            x = x // check
        else:
            check += 1
            if check > x:
                break
    return dict(primes)

primes = make_prime_dict(M)

Q = max(primes.values())
fact = [1]
fact_inv = [1]
for i in range(Q+N):
    new_fact = fact[-1] * (i+1) % MOD
    fact.append(new_fact)
    fact_inv.append(pow(new_fact, MOD - 2, MOD))

def mod_comb(n, r, mod):
    return fact[n] * fact_inv[n - r] % mod * fact_inv[r] % mod

res = 1
for q in primes.values():
    res *= mod_comb(q + N - 1, q, MOD)
    res %= MOD

print(res)

### FIXED CODE ###

from collections import defaultdict as dd

N, M = map(int, input().split())
MOD = 10 ** 9 + 7
# a1 x a2 x .. x aN = M となる数列{ai}が何通りあるか
# まずは素因数分解
def make_prime_dict(x):
    primes = dd(int)
    check = 2
    while True:
        if x % check == 0:
            primes[check] += 1
            x = x // check
        else:
            check += 1
            if check > x:
                break
    return dict(primes)

primes = make_prime_dict(M)
if len(primes) == 0:
    print(1)
    exit()
Q = max(primes.values())
fact = [1]
fact_inv = [1]
for i in range(Q+N):
    new_fact = fact[-1] * (i+1) % MOD
    fact.append(new_fact)
    fact_inv.append(pow(new_fact, MOD - 2, MOD))

def mod_comb(n, r, mod):
    return fact[n] * fact_inv[n - r] % mod * fact_inv[r] % mod

res = 1
for q in primes.values():
    res *= mod_comb(q + N - 1, q, MOD)
    res %= MOD

print(res)
def minandmax(bottom,up,mod): #bottom< n < upなるmodで割り切れるnの値の最大値と最小値を返す
    if bottom%mod == 0:
        mnm = bottom
    else:
        mnm = bottom + (mod-bottom%mod)
        if mnm > up:
            mnm = None
    if up%mod == 0:
        mxm = up
    else:
        mxm = up - up%mod
        if mxm < bottom:
            mxm = None
    ans = [mnm,mxm]
    return ans

k = int(input())
a = list(map(int,input().split()))
i = k-1
bottom = 2
up = 2

check = True
if a[-1] != 2:
    check = False
while i >= 1 and check:
    bottom = minandmax(bottom,up+a[i]-1,a[i-1])[0]
    up = minandmax(bottom,up+a[i]-1,a[i-1])[1]
    if bottom == None and up == None:
        check = False
    elif bottom == None:
        bottom = up
    elif up == None:
        up = bottom
    i += -1

if check:
    bottom = minandmax(bottom,bottom+a[0]-1,1)[0]
    up = minandmax(up,up+a[0]-1,1)[1]
    print(bottom,up)
else:
    print("-1")

### FIXED CODE ###

def minandmax(bottom,up,mod): #bottom< n < upなるmodで割り切れるnの値の最大値と最小値を返す
    if bottom%mod == 0:
        mnm = bottom
    else:
        mnm = bottom + (mod-bottom%mod)
        if mnm > up:
            mnm = None
    if up%mod == 0:
        mxm = up
    else:
        mxm = up - up%mod
        if mxm < bottom:
            mxm = None
    ans = [mnm,mxm]
    return ans

k = int(input())
a = list(map(int,input().split()))
i = k-1
bottom = 2
up = 2

check = True
if a[-1] != 2:
    check = False
while i >= 1 and check:
    nbottom = minandmax(bottom,up+a[i]-1,a[i-1])[0]
    nup = minandmax(bottom,up+a[i]-1,a[i-1])[1]
    if nbottom == None and nup == None:
        check = False
    elif nbottom == None:
        nbottom = nup
    elif nup == None:
        nup = nbottom
    i += -1
    bottom = nbottom
    up = nup

if check:
    bottom = minandmax(bottom,bottom+a[0]-1,1)[0]
    up = minandmax(up,up+a[0]-1,1)[1]
    print(bottom,up)
else:
    print("-1")
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]

n,q = LI()

v = [[] for i in range(n)]
for i in range(n-1):
	a,b = LI()
	a -= 1
	b -= 1
	v[a].append(b)

f = [0]*n
for i in range(q):
	p,x = LI()
	p -= 1
	f[p] += x

def dfs(x,d,s):
	for y in v[x]:
		if d[y]:
			s += f[y]
			ans[y] = s
			d[y] = 0
			dfs(y,d,s)
			s -= f[y]

ans = [0]*n
d = [1]*n
d[0] = 0
ans[0] = f[0]
s = f[0]
dfs(0,d,s)
print(*ans)
d = [1]*n
d[0] = 0
ans[0] = f[0]
s = f[0]
dfs(0,d,s)
print(*ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

def LI(): return [int(x) for x in sys.stdin.readline().split()]

n,q = LI()

v = [[] for i in range(n)]
for i in range(n-1):
	a,b = LI()
	a -= 1
	b -= 1
	v[a].append(b)
	v[b].append(a)

f = [0]*n
for i in range(q):
	p,x = LI()
	p -= 1
	f[p] += x

def dfs(x,d,s):
	for y in v[x]:
		if d[y]:
			s += f[y]
			ans[y] = s
			d[y] = 0
			dfs(y,d,s)
			s -= f[y]

ans = [0]*n
d = [1]*n
d[0] = 0
ans[0] = f[0]
s = f[0]
dfs(0,d,s)
print(*ans)