Harryxun/stf_run huggingface dataset:
import itertools
import numpy as np
from scipy.special import comb

mod = 998244353

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

# DP = [[0]*N for _ in range(N)]
# DP[0][0] = M

# DP = []


# for n in range(1,N):
# 	for k in range(N):
# 		if k==0:
# 			DP[n][k] = DP[n-1][k]*(M-1) % mod
# 		else:
# 			DP[n][k] = (DP[n-1][k]*(M-1) + DP[n][k-1]) % mod

# ans = sum(DP[N-1][:(K+1)]) % mod
# print(ans)

ans = 0
for k in range(1,K+1):
	ans += comb(N, k-1)*(M-1)**(N-k) % mod

print(int(ans*M) % mod)

### FIXED CODE ###

MOD = 998244353
MAX = 510000
fac = [1,1] # factorial
finv = [1,1] # inverse of factorial
inv = [None, 1] # inverse

def comb_init():
	for i in range(2, MAX):
		fac.append(fac[i-1] * i % MOD)
		inv.append(MOD - inv[MOD % i] * (MOD//i) % MOD)
		finv.append(finv[i-1] * inv[i] % MOD)

def inverse_mod(a):
	""" Calculate inverse of the integer in a modulo MOD """
	return pow(a, MOD-2, MOD)

def comb_mod(n, r):
	""" Calculate nCr modulo MOD. """
	if n < r: return 0
	if n < 0 or r < 0: return 0
	return fac[n]* (finv[r]*finv[n-r] % MOD) % MOD

def solve(n, m, k):
	ans = 0
	for k in range(K+1):
		ans = (ans + m*(comb_mod(n-1,k)*pow(m-1, n-k-1, MOD) % MOD) % MOD) % MOD
	return ans

comb_init()
N, M, K = map(int, input().split())
print(solve(N, M, K))
n = int(input())
v = map(int, input().split())
c = map(int, input().split())
ans = 0

for i in range(n):
  if v[i] - c[i] > 0:
    ans += v[i] - c[i]
print(ans)

### FIXED CODE ###

n = int(input())
v = list(map(int, input().split()))
c = list(map(int, input().split()))
ans = 0

for i in range(n):
  if v[i] - c[i] > 0:
    ans += v[i] - c[i]
print(ans)
from math import factorial

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

for i, s_i in enumerate(s):
    s_l = list(s_i)
    s_l.sort()
    a = ""
    for c in s_l:
        a += c
    s[i] = a

cnt = 0
count_dict = {}
for j in range(N):
    count_dict[s[j]] = 0
for k in range(N):
    count_dict[s[k]] += 1

for v in count_dict.values():
    if v >= 2:
        cnt += int(factorial(v) / factorial(2) / factorial(v - 2))

print(cnt)

### FIXED CODE ###

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result


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

for i, s_i in enumerate(s):
    s_l = list(s_i)
    s_l.sort()
    a = ""
    for c in s_l:
        a += c
    s[i] = a

cnt = 0
count_dict = {}
for j in range(N):
    count_dict[s[j]] = 0
for k in range(N):
    count_dict[s[k]] += 1

for v in count_dict.values():
    if v >= 2:
        # cnt += int(factorial(v)) / int(factorial(2)) / int(factorial(v - 2))
        cnt += cmb(v, 2)

print(cnt)
a=int(input())
b="Christmas"
for i in range(25-a)
	b+=" Eve"
print(b)


### FIXED CODE ###

a=int(input())
b="Christmas"
for i in range(25-a):
	b+=" Eve"
print(b)
h, w = list(map(int, input().strip().split()))
s = [list(input) for i in range(h)]

for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            continue
        count = 0
        for a in range(i-1, i+2):
            for b in range(j-1, j+2):
                c += all((min(a,b)>=0, a < h, b < w)) and s[a][b] == '#'

            if s[i][j] == '.':
                s[i][j] = c
for c in s:
    print(c)

### FIXED CODE ###

H, W = map(int, input().split())
S = [input() for x in range(H)]

res = []

for i in range(H):
    r = []
    for j in range(W):
        if S[i][j] == '#':
            r.append('#')
        else:
            count = 0
            for d in [(-1, 1), (0, 1), (1, 1), (-1, 0), (0, 0), (1, 0), (-1, -1), (0, -1), (1, -1)]:
                x = i+d[0]
                y = j+d[1]

                if (0 <= x < H) and (0 <= y < W) and S[x][y] == '#':
                    count += 1
            r.append(count)
    res.append(r)

for i in range(H):
    print(''.join(map(str, res[i])))
N = int(input())
i = 1
for i in N+1:
  if not i % 3 == 0 or i % 5 == 0:
    m += i

print (m)

### FIXED CODE ###

N = int(input())
m = 0
for i in range(N+1):
  if not (i % 3 == 0 or i % 5 == 0):
    m += i
 
print (m)
n=int(input())
a=list(map(int,input().split()))
if 0 in a:
    print(0)
else:
    s=1
    for i in a:
    s=s*i
    if s>10**18:
        s=-1
        break
    print(s)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
if 0 in a:
    print(0)
else:
    s=1
    for i in a:
        s=s*i
        if s>10**18:
            s=-1
            break
    print(s)
s=list(map(int,input().split()))
x=0
for i in 1:
  s[i] = 1
  x+=1
print(x)

### FIXED CODE ###

s=input()
print(s.count("1"))
n = int(input())
a = list(map(int, input().split()))
a1 = []
a2 = []
for i in range(n):
    if i % 2 == 0:
        a1.append(a[i])
    else:
        a2.append(a[i])
if n % 2 == 0:
    rev = list(reversed(a2))
    print(*rev, *a1)
else:
    rev = list(reversed(a1))
    print(*rev, *a2)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a1 = []
a2 = []
for i in range(n):
    if i % 2 == 0:
        a1.append(a[i])
    else:
        a2.append(a[i])
if n % 2 == 0:
    a2.reverse()
    print(*a2+a1)
else:
    a1.reverse()
    print(*a1+a2)
N,X = map(int,input().split())
L = list(map(int,input().split()))
C = 1
M = 0

for i in range(N + 1):
    M = M + L[i]
    if M >= X:
        print(C)
        exit(0)
    
    C = C + 1

print(C)

### FIXED CODE ###

N,X = map(int,input().split())
L = list(map(int,input().split()))
C = 1
M = 0

for i in range(N):
    M = M + L[i]
    if M > X:
        print(C)
        exit(0)
    
    C = C + 1

print(C)
while(1):
	n, x = map(int, input().split())
	t = 0
	if n == x == 0:
		break
	for i in range(1, n+1):
		for j in range(i+1, n+1):
			for k in range(k+1, n+1):
				if i+j+k == x:
					if i != j and j != k and k != i:
						t += 1
						#print(i, j, k)
	print(t)

### FIXED CODE ###

while(1):
	n, x = map(int, input().split())
	t = 0
	if n == x == 0:
		break
	for i in range(1, n+1):
		for j in range(i+1, n+1):
			for k in range(j+1, n+1):
				if i+j+k == x:
					if i != j and j != k and k != i:
						t += 1
						#print(i, j, k)
	print(t)
import math
import sys
from itertools import accumulate
from functools import reduce
import queue
from fractions import gcd

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

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

sys.setrecursionlimit(10000)

mod = 1000000007

"""
# 0埋め, 小数点出力桁指定時のときの出力
a = 100
b = 0.987654321
print("{0:06d}-{1:6f}".format(a,b))
000100-0.987654

# 文字列をリストに格納
char_list = list("abcd") # ["a","b","c","d"]

# 標準入力取得
## 文字列
    = sys.stdin.readline().rstrip()
    = list(sys.stdin.readline().rstrip())
    = [list(list(sys.stdin.readline().rstrip())) for i in range(h)] #文字列を分解して二次元配列入力

## 数値
    = int(sys.stdin.readline())
    = map(int, sys.stdin.readline().split())
    = list(map(int, sys.stdin.readline().split()))
    = [list(map(int,list(sys.stdin.readline().split()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき
"""

if __name__ == "__main__":
    h,w = map(int, sys.stdin.readline().split())
    s =  [list(list(sys.stdin.readline().rstrip())) for i in range(h)]
    flag=0
    for i in range(h):
        for j in range(w):
            if s[i][j] == "#":
                if s[i-1][j] =="." and s[i+1][j] =="." and s[i][j-1] =="."  and s[i][j+1] ==".":
                    flag = 1
    print("Yes" if flag==0 else "No")

### FIXED CODE ###

H,W=map(int,input().split())
S=["."+input()+"." for i in range(H)]
S=["."*(W+2)]+S+["."*(W+2)]
flag=0
for i in range(H):
    for j in range(W):
        if S[i][j]=="#":
            if S[i-1][j]=="." and S[i+1][j]=="." and S[i][j-1]=="." and S[i][j+1]==".":
                flag=1
print("Yes" if flag==0 else "No")
field = []
w = 0
h = 0


def main():
    global field, w, h
    while True:
        h, w = map(int, input().split())
        if h == 0 and w == 0:
            break
        count = 0
        field = [[0] * w for _ in range(h)]
        for y in range(h):
            kinds = [_ for _ in input()]
            arrangement(kinds, y)

        for y in range(h):
            for x in range(w):
                if field[y][x] != -1:
                    dfs(field[y][x], x, y)
                    count += 1

        print(count)


def arrangement(kinds, y):
    global field
    for i, kind in enumerate(kinds):
        field[y][i] = kind


def dfs(kind, x, y):
    global field
    field[y][x] = -1
    for dx, dy in zip([0, 0, -1, 1], [1, -1, 0, 0]):
        next_x = x + dx
        next_y = y + dy
        if next_x < 0 or next_y < 0 or next_x >= w or next_y >= h:
            continue
        if field[next_y][next_x] != kind:
            continue
        dfs(field[next_y][next_x], next_x, next_y)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(20000)

field = []
w = 0
h = 0


def main():
    global field, w, h
    while True:
        h, w = map(int, input().split())
        if h == 0 and w == 0:
            break
        count = 0
        field = []
        [field.append(list(input())) for _ in range(h)]
        for y in range(h):
            for x in range(w):
                if field[y][x] != -1:
                    dfs(field[y][x], x, y)
                    count += 1
        print(count)


def dfs(kind, x, y):
    global field
    field[y][x] = -1
    for dx, dy in zip([0, 0, -1, 1], [1, -1, 0, 0]):
        next_x = x + dx
        next_y = y + dy
        if next_x < 0 or next_y < 0 or next_x >= w or next_y >= h \
                or field[next_y][next_x] != kind:
            continue
        dfs(field[next_y][next_x], next_x, next_y)


if __name__ == '__main__':
    main()
a=int(input())
b=int(input())
c=int(input())

print(a*b/2)


### FIXED CODE ###

a=input()
x=[ int(y) for y in a.split() ]
print(x[0]*x[1]//2)
a, b = map(int.input(),split())

print(a*b)

### FIXED CODE ###

a, b = map(int, input().split())
ans = a*b
print(ans)
def main():
    W, H, x, y = map(int, input().split())

    area = 0
    pat = 0

    if (x == 0 and y == 0) or (x == 0 and y == H) or (x == W and Y == 0) or (x == W and y == H):
        area = W*H/2.0
        
    else:
        area_H = 0
        area_V = 0

        area_H = min(H - y, y) * W
        area_V = min(x, W - x) * H

        if area_H == area_V:
            pat = 1

        area = max(area_H, area_V)
        
    print(area, pat)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    W, H, x, y = map(int, input().split())
    pat = 0

    if x == W/2 and y == H/2:
        pat = 1

    print((W*H)/2.0, pat)

if __name__ == "__main__":
    main()
n, p = map(int, input().split())
 
s = list(input())
ans = 0
if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i + 1
else:
    d = [0] * (n + 1)
    ten = 1
    for i in range(n - 1, -1, -1):
        a = int(s[i]) * ten % p
        sum+=a
        ten *= 10
        ten %= p
        d[i]= sum % p
    cnt = [0] * p
    for i in range(n, -1, -1):
        cnt[d[i]] += 1
    for  i in cnt:
        ans+=i*(i-1)/2
print(d)
print(int(ans))

### FIXED CODE ###

n, p = map(int, input().split())
 
s = list(input())
ans = 0
if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i + 1
else:
    d = [0] * (n + 1)
    ten = 1
    for i in range(n - 1, -1, -1):
        a = int(s[i]) * ten % p
        ten *= 10
        ten %= p
        d[i - 1] = (d[i] + a) % p
    cnt = [0] * p
    for i in range(n, -1, -1):
        cnt[d[i]] += 1
    for  i in cnt:
        ans+=i*(i-1)/2

print(int(ans))
S=set(input())
A={"a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"}
D=sorted(list(A-S))
print(D[0])

### FIXED CODE ###

S=set(input())
A={"a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"}
D=sorted(list(A-S))
if len(D)==0:
  print("None")
else:
  print(D[0])
from sys import setrecursionlimit
setrecursionlimit(10 ** 8)

A = input()
B = input()

class Source():
  def __init__(self, S):
    self.S = S
    self.pos = 0
   
  
def peek(S):
  return S.S[S.pos] if S.pos < len(S.S) else -1

def next(S):
  print(S.S[S.pos], end='')
  S.pos += 1
  
def tree(S):
  next(S)
  if peek(S) == ')':
    next(S)
    return -1
  left = tree(S)
  center = root(S)
  right = tree(S)
  next(S)
  
def root(S):
  res = 0
  next(S)
  while peek(S) != ']':
    res += res * 10 + int(peek(S))
    next(S)
  next(S)
  
  return res
  
tree(Source('(' + A + ')'))
  

### FIXED CODE ###

p, q, r = [int(i) for i in input().split()]

print(min(p + q, q + r, r + p))
N,K,M =  map(int,input().split())
A =  list(map(int,input().split()))

result = N*M - sum(A) 
if result > K:
    print("-1")
elif result <=0:
    print("0")
else:
    print(result)

### FIXED CODE ###

C = input()
print(chr(ord(C) + 1))
import collections
n,x,m=map(int,input().split())
start,end,loopcnt=0,0,0
a={x:0}
wk=x
for i in range(1,m):
  wk=(wk*wk)%m
  if not wk in a:
    a[wk]=i
  else:
    start=a[wk]
    end=i
    break
a=sorted(a.items(),key=lambda x:x[1])
koteiindex=min(n,start)
koteiwa=0
for i in range(koteiindex):
  koteiwa+=a[i][0]
loopcnt=(n-koteiindex)//(end-start)
loopindex=start-1+(n-koteiindex)%(end-start)
loopwa=0
amariwa=0
for i in range(start,end):
  if i<=loopindex:
    amariwa+=a[i][0]
  loopwa+=a[i][0]
ans=koteiwa+loopwa*loopcnt+amariwa
print(ans)


### FIXED CODE ###

import collections
n,x,m=map(int,input().split())
if n==1 or x==0:
  print(x)
  exit()
start,end,loopcnt=0,0,0
a={x:0}
wk=x
for i in range(1,m):
  wk=(wk*wk)%m
  if not wk in a:
    a[wk]=i
  else:
    start=a[wk]
    end=i
    break
a=sorted(a.items(),key=lambda x:x[1])
koteiindex=min(n,start)
koteiwa=0
for i in range(koteiindex):
  koteiwa+=a[i][0]
loopcnt=(n-koteiindex)//(end-start)
loopindex=start-1+(n-koteiindex)%(end-start)
loopwa=0
amariwa=0
for i in range(start,end):
  if i<=loopindex:
    amariwa+=a[i][0]
  loopwa+=a[i][0]
ans=koteiwa+loopwa*loopcnt+amariwa
print(ans)
a,b,c,d = map(int, input().split())


n = c // b
m = c % b

if m != 0:

    if a - n * d <= 0 | a - (n-1) * d <= 0:
        print('No')

    else:
        print('Yes')


if m == 0:
    if a - (n-2) * d <= 0 | a - (n-1) * d <= 0:
        print('No')

    else:
        print('Yes')

### FIXED CODE ###

s,w = map(int,input().split())

if s <= w :
    print('unsafe')

else :
    print('safe')
N,M = map(int,input().split())
s,c = [map(int,input().split()) for i in range(M)]
l = []
first = []
second = []
third = []
for i in range(M):
  if s[i] == 1:
    first.append(c[i])
  elif s[i] == 2:
    second.append(c[i])
  elif s[i] == 3:
    third.append(c[i])
if first == []:
  print(-1)
elif second == []:
  second.append(0)
elif third == []:
  third.append(0)
l.append(min(first))
l.append(min(second))
l.append(min(third))
l = ''.join(str(n) for n in l)
print(l)



### FIXED CODE ###

N,M = map(int,input().split())
sc=[list(map(int,input().split()))for _ in range(M)]
ans = -1
for i in range(1000):
  s = str(i)
  if len(s) == N:
    flg = 0
    for a,b in sc:
      if int(s[a-1]) != b:
        flg = 1
    if flg == 0:
      ans = i
      break
print(ans)
n = int(input())
d = [int(i) for input().split()]
s = []
for i in range(n):
	for j in range(i):
		s.append(d[i]*d[j])
l = s.size()
for i in range(l):
	print(s[i])


### FIXED CODE ###

n = int(input())
d = [int(i) for i in input().split()]
s = []
for i in range(n):
	for j in range(i):
		s.append(d[i]*d[j])
print(sum(s))
n = int(input())
a = 2
b = 1
if n < 2:
    print(n)
else:
    for i in range(n - 1):
        c = a + b
        a = b
        b = c
print(c)


### FIXED CODE ###

n = int(input())
a = 2
b = 1
if n == 0:
    print(2)
elif n == 1:
    print(1)
else:
    for i in range(n - 1):
        c = a + b
        a = b
        b = c
    print(c)
n,A,B=map(int,input().split())
s=list(input())
cnt=0
cnt_b=0
for i in range(n):
	if s[i]=='a' and cnt<a+b:
		print('Yes')
		cnt+=1
	elif s[i]=='b' and cnt<A+B and cnt_b<=B:
			print('Yes')
	else:
		print('No')

### FIXED CODE ###

n,A,B=map(int,input().split())
s=list(input())
cnt=0
cnt_b=0
for i in range(n):
	if s[i]=='a' and cnt<A+B:
		print('Yes')
		cnt+=1
	elif s[i]=='b' and cnt<A+B and cnt_b<B:
		print('Yes')
		cnt_b+=1
		cnt+=1
	else:
		print('No')
import fractions
N, M = map(int, input().split())
S = input()
T = input()
if S[0] != T[0]:
    print(-1)
else:
    lcm = N*M // fractions.gcd(N, M)
    count = 1
    tmp = lcm // N
    tmp2 = lcm // M
    flag = False

    tmp_s = [""] * (lcm * count)
    for i in range(N):
        tmp_s[((lcm*count) // N) * i] = S[i]
    for i in range(M):
        if tmp_s[((lcm*count) // M) * i] != "" and tmp_s[((lcm*count) // M) * i] != T[i]:
            count += 1
            print(-1)
            exit(0)
    print(lcm)


### FIXED CODE ###

import collections
import fractions
N, M = map(int, input().split())
S = input()
T = input()
lcm = (N*M) // fractions.gcd(N, M)
if S[0] != T[0]:
    print(-1)
elif N == M and S != T:
    print(-1)
else:
    tmp = lcm // N
    tmp2 = lcm // M
    tmp_s = collections.defaultdict(str)
    for i in range(N):
        tmp_s[tmp*i] = S[i]

    for i in range(M):
        if tmp2*i in tmp_s:
            if T[i] != tmp_s[tmp2*i]:
                print(-1)
                exit(0)
    print(lcm)
n,k = map(int,input().split())
an = list(map(int, input().split()))
copyan = an[:]
i = copyan[0]
copyan[0]=10**6
movecount = 1

if i != 1:
    while True:
        memo = i
        if k == movecount:
            print(i)
            exit()
        i = copyan[i-1]
        
        
        if i >=30000:
            yokei = i%(10**6)
            
            break
        copyan[memo-1]=10**6 + movecount
        movecount += 1
        
else:
    print(1)
    exit()
roopnum = movecount - yokei
x = (k-yokei)%roopnum #移動する回数

ans = copyan.index(10**6+yokei+x) +1
print(ans)


### FIXED CODE ###

n,k = map(int,input().split())
an = list(map(int, input().split()))
copyan = an[:]
i = copyan[0]
copyan[0]=10**6
movecount = 1

if i != 1:
    while True:
        memo = i
        if k == movecount:
            print(i)
            
            exit()
        i = copyan[i-1]
        
        if i >=300000:
            yokei = i%(10**6)         
            break
        copyan[memo-1]=10**6 + movecount
        movecount += 1
        
else:
    print(1)
    exit()
roopnum = movecount - yokei
x = (k-yokei)%roopnum

ans = copyan.index(10**6+yokei+x) +1
print(ans)
import math
a, b, c, d = map(int, input().split())

# 最小公倍数
c_d = c * d / math.gcd(c, d)

def check(cc):
    if a%cc == 0:
        tmp_a = a
    else:
        tmp_a = cc*(a//cc+1)
    if b%cc == 0:
        tmp_b = b
    else:
        tmp_b = cc*(b//cc)

    #print('a, b')
    #print(tmp_a, tmp_b)
    if tmp_a > b:
        return 0
    elif tmp_b < a:
        return 0
    tmp = tmp_b-tmp_a

    return (tmp // cc) + 1

# c
tmp_1 = check(c)
#d
tmp_2 = check(d)

tmp_3 = check(c_d)


#print(tmp_1, tmp_2, tmp_3)


print(int((b-a)-(tmp_1+tmp_2-tmp_3*2)))


### FIXED CODE ###

import fractions

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

c_d = (c * d) // fractions.gcd(c, d)

a -= 1

tmp_b = b - (b//c + b//d - b//c_d)
tmp_a = a - (a//c + a//d - a//c_d)

print(tmp_b-tmp_a)
nums = input().spilt(" ")
num1 = int(nums[0])
num2 = int(nums[1])
if num2 % num1 == 0:
    print(num1+num2)
else:
    print(num2-num1)

### FIXED CODE ###

nums = input().split(" ")
num1 = int(nums[0])
num2 = int(nums[1])
if num2 % num1 == 0:
  print(num1+num2)
else:
  print(num2-num1)
N = int(input())
K = int(input())
S = N // K
Answer = abs(N - K*S)
if abs(Answer - K) <= Answer:
    Answer = abs(Answer - K)
print(Answer)

### FIXED CODE ###

N,K = map(int,input().split())
S = N // K
Answer = abs(N - K*S)
if abs(Answer - K) <= Answer:
    Answer = abs(Answer - K)
print(Answer)
N,Q = map(int,input().split())
adj = [ [] for _ in range(N) ]
for _ in range(N-1):
  u,v = map(int,input().split())
  u -= 1
  v -= 1
  adj[u].append(v)
scores = [0] * N
for _ in range(Q):
  u,p = map(int,input().split())
  u -= 1
  scores[u] += p

res = [0] * N
def dfs(n, p, s):
  res[n] = s
  for nei in adj[n]:
    if nei != p:
      dfs(nei, n, s+scores[nei])

dfs(0,-1,scores[0])

print(" ".join(map(str, res)))

### FIXED CODE ###

from collections import deque
N,Q = map(int,input().split())
adj = [ [] for _ in range(N) ]
for _ in range(N-1):
  u,v = map(int,input().split())
  u -= 1
  v -= 1
  adj[u].append(v)
  adj[v].append(u)

scores = [0] * N
for _ in range(Q):
  u,p = map(int,input().split())
  u -= 1
  scores[u] += p

res = [0] * N
visited = [False] * N
q = deque([(scores[0], 0)])
while q:
  s,n = q.popleft()
  res[n] = s
  visited[n] = True

  for nei in adj[n]:
    if not visited[nei]:
      q.append((s+scores[nei], nei))

print(" ".join(map(str, res)))
# _*_ coding: utf-8 _*_

n, k = [int(e) for e in input().strip().split(' ')]
s = input().strip()

cnts = []
ans = 0
# denote whether the first block is 0 or 1
tmp, cnt = s[0], 0
flag = s[0]

for i in range(n):
    if s[i] == tmp:
        cnt += 1
    else: # here tmp should be cleared
        cnts.append(cnt)
        cnt = 1
    tmp = s[i]
cnts.append(cnt)

n_zero = (len(cnts) + 1) // 2 if flag == 0 else len(cnts) // 2

if n_zero <= k:
     ans = sum(cnts)
else:
    ans = 0
    for inx in range(flag, len(cnts), 2):
        start = max(0, inx - 1)
        end = min(inx + 2 * k, len(cnts))
        tmp = sum(cnts[start: end])
        if tmp > ans:
            ans = tmp

print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
s = [int(x) for x in list(input())]

state = 1
cnt = 0
l = []
for e in s:
    if e != state:
        l.append(cnt)
        cnt = 1
        state = e
    else:
        cnt += 1

if cnt != 0:
    l.append(cnt)


if len(l) % 2 == 1:
    l.append(0)

Add = 2 * k + 1
ruiseki = [0]

for i, e in enumerate(l):
    ruiseki.append(ruiseki[i] + l[i])

answer = 0
for i in range(0, len(l), 2):
    left = i
    right = min(i + Add, len(l))
    tmp = ruiseki[right] - ruiseki[left]
    answer = max(tmp, answer)

print(answer)
S=input()
if S[：4]=='YAKI'：
    print('Yes')
else：
    print('No')
 


### FIXED CODE ###

S = input()
if len(S) < 4:
    print("No")
    exit(0)
if S[:4] == "YAKI":
    print("Yes")
else:
    print("No")
n,k=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):
    a[i]-=1
b=[0]
c=dict()
visited=[False]*n
visited[0]=True
c[0]=0
cnt=0
dap=0
while True:
    n=b[-1]
    if visited[a[n]]:
        dap=c[a[n]] 
        break
    visited[a[n]]=True
    b.append(a[n])
    c[n]=cnt
    cnt+=1
l=len(b)
print(b[(k-dap)%(l-dap)+dap]+1)

### FIXED CODE ###

N,k=map(int,input().split())
a=list(map(int,input().split()))
for i in range(N):
    a[i]-=1
if a[0]==0:print(1);exit()
c=dict()
visited=[False]*N
visited[0]=True
c[0]=0
cnt=0
dap=0
n=0
b=[0]
while True:
    n=a[n]
    if visited[n]:
        dap=c[n] 
        break
    visited[n]=True
    b.append(n)
    cnt+=1
    c[n]=cnt
l=len(c)
if k<dap:
    print(b[k]+1)
else:
    print(b[(k-dap)%(l-dap)+dap]+1)
# -*- coding: utf-8 -*-
N, K = map(int, input().split())
array = list(map(int, input().split()))

sum = 0
max = 0
max_index = K

for i in range(K):
    sum += array[i]
    max = sum

for i in range(K, N):
    sum += array[i] - array[i - K]
    if sum > max:
        max = sum
        max_index = i

E = [(array[x] + 1) / 2 for x in range(max_index - K + 1, max_index + 1)]

sum2 = 0
for x in E:
    sum2 += x

print(sum2)

### FIXED CODE ###

# -*- coding: utf-8 -*-
N, K = map(int, input().split())
array = list(map(int, input().split()))

sum = 0
max = 0

for i in range(K):
    sum += array[i]
    max = sum

for i in range(K, N):
    sum += array[i] - array[i - K]
    if sum > max:
        max = sum

E = (max + K) / 2
print(E)