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

#!/usr/bin/env python
# coding: utf-8

# In[1]:
import sys
sys.setrecursionlimit(1000000)


N, u, v = map(int, input().split())
u = u - 1
v = v - 1


# In[2]:


eda = [[] for _ in range(N)]
for _ in range(N-1):
    A, B = map(int, input().split())
    eda[A-1].append(B-1)
    eda[B-1].append(A-1)


# In[3]:


eda


# In[ ]:





# In[4]:


def dfs(n1, n0):
    houmon[n1] = True
    par[n1] = n0
    for n2 in eda[n1]:
        if not houmon[n2]:
            dfs(n2, n1)
    


# In[5]:


houmon = [False] * N
par = [0] * N
dfs(v, v)


# In[6]:


par


# In[7]:


dis = 0
n = u
while n != v:
    n = par[n]
    dis += 1


# In[8]:


dis


# In[9]:


n = u
for _ in range((dis - 1) // 2):
    n = par[n]


# In[10]:


n


# In[11]:


def dfs2(n1):
    ret = 0
    for n2 in eda[n1]:
        if n2 == par[n1]:
            continue
        ret = max(ret, dfs2(n2) + 1)
    return ret


# In[12]:


y = (dis - 1) // 2
x = dis - y
z = dfs2(n)


# In[13]:


print(y + z + 1 if dis % 2 == 0 else y + z)



### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[21]:


N, u, v = map(int, input().split())
u = u - 1
v = v - 1


# In[22]:


eda = [[] for _ in range(N)]
for _ in range(N-1):
    A, B = map(int, input().split())
    eda[A-1].append(B-1)
    eda[B-1].append(A-1)


# In[25]:


par = [0] * N
# depth = [0] * N

stack = [v]
par[v] = -1

while stack:
    n1 = stack.pop()
    for n2 in eda[n1]:
        if n2 == par[n1]:
            continue
        par[n2] = n1
#         depth[n2] = depth[n1] + 1
        stack.append(n2)
        


# In[26]:


par


# In[27]:


dis = 0
n = u
while n != v:
    n = par[n]
    dis += 1


# In[28]:


n = u
for _ in range((dis - 1) // 2):
    n = par[n]


# In[29]:


y = (dis - 1) // 2
x = dis - y
# z = depth[n]


# In[38]:


stack = [n]
depth = [0] * N
maxd = 0

while stack:
    n1 = stack.pop()
    for n2 in eda[n1]:
        if n2 == par[n1]:
            continue
        depth[n2] = depth[n1] + 1
        maxd = max(maxd, depth[n2])
        stack.append(n2)
        


# In[41]:


z = maxd


# In[43]:


if dis % 2 == 0:
    print(y + z + 1)
else:
    print(y + z)


# In[ ]:
### BUGGY CODE ###

import math
# from itertools import product
from functools import reduce

def main():
    def gcd(*numbers): return reduce(math.gcd, numbers)
    K = int(input())
    ans = 0
#     valiation = list(itertools.product(range(1, K+1), repeat=3))
#     for v in valiation:
#         ans += gcd(v)
    for i in range(1, K+1):
        for j in range(1, K+1):
            for k in range(1, K+1):
                ans += gcd(i, j, k)
    print(ans)
        
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

import math
# from itertools import product
from functools import reduce

def main():
#     def gcd(*numbers): return reduce(math.gcd, numbers)
    K = int(input())
    ans = 0
#     valiation = list(itertools.product(range(1, K+1), repeat=3))
#     for v in valiation:
#         ans += gcd(v)
    for i in range(1, K+1):
        for j in range(1, K+1):
            for k in range(1, K+1):
                ans += math.gcd(math.gcd(i, j), k)
    print(ans)
        
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

N,MOD = map(int,input().split())
if N == 1:
    print(1)
    exit()
graph = [[] for _ in range(N)]
for row in sys.stdin.readlines():
    x,y = map(int,row.split())
    graph[x-1].append(y-1)
    graph[y-1].append(x-1)

ldp = [None] * N
rdp = [None] * N

def dfs_1(v=0,parent=None):
    # 子ごとに、そこを黒くして適切 or 完全白
    graph[v] = [w for w in graph[v] if w != parent]
    ldp[v] = [1] * (len(graph[v])+1)
    rdp[v] = [1] * (len(graph[v])+1)
    vals = [dfs_1(w,v)+1 for w in graph[v]]
    for i,x in enumerate(vals,1):
        ldp[v][i] = ldp[v][i-1] * x % MOD
    for i,x in enumerate(reversed(vals),1):
        rdp[v][-i-1] = rdp[v][-i] * x % MOD
    return ldp[v][-1]

dfs_1()

def dfs_2(v=0,x=1):
    # それぞれの子以外の情報をマージして、子に渡さなければいけない
    dp[v] = x * ldp[v][-1] % MOD
    for w,p,q in zip(graph[v],ldp[v][:-1],rdp[v][1:]):
        dfs_2(w,x*p*q%MOD+1)

dp = [None] * N
dfs_2()

print('\n'.join(map(str,dp)))

### FIXED CODE ###

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

N,MOD = map(int,input().split())
if N == 1:
    print(1)
    exit()
graph = [set() for _ in range(N)]
for row in sys.stdin.readlines():
    x,y = map(int,row.split())
    graph[x-1].add(y-1)
    graph[y-1].add(x-1)

ldp = [None] * N
rdp = [None] * N

def dfs_1(v=0,parent=None):
    # 子ごとに、そこを黒くして適切 or 完全白
    graph[v].discard(parent)
    ldp[v] = [1] * (len(graph[v])+1)
    rdp[v] = [1] * (len(graph[v])+1)
    vals = [dfs_1(w,v)+1 for w in graph[v]]
    for i,x in enumerate(vals,1):
        ldp[v][i] = ldp[v][i-1] * x % MOD
    for i,x in enumerate(reversed(vals),1):
        rdp[v][-i-1] = rdp[v][-i] * x % MOD
    return ldp[v][-1]

dfs_1()

dp = [None] * N
q = [(0,1)]
while q:
    v,x = q.pop()
    dp[v] = x*ldp[v][-1]%MOD
    for w,L,R in zip(graph[v],ldp[v][:-1],rdp[v][1:]):
        q.append((w,x*L*R%MOD+1))

print('\n'.join(map(str,dp)))
### BUGGY CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
dp = [10**9] * N

for i in range(N):
    if i == 0:
        dp[0] = 0
    elif i == 1:
        dp[1] = abs(h[0]-h[1])
    else:
        for j in range(1, K+1):
            if j > i:
                break
            dp[i] = min(dp[i], dp[i - j] + abs(h[i - j] - h[i]))

print(dp[N-1])

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [0] * n

for i in range(n):
    if i == 0:
        dp[0] = 0
    elif i == 1:
        dp[1] = abs(h[0]-h[1])
    else:
        costs = []
        for j in range(1, k+1):
            if j > i:
                break
            if abs(h[i-j]-h[i]) == 0:
                costs.append(dp[i-j])
                break
            costs.append(dp[i-j] + abs(h[i-j]-h[i]))

        # if i == 3:
        #     print(costs)
        dp[i] = min(costs)

#print(dp)
print(dp[n-1])
### 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=[a+b for a in A for b in B]
AB.sort(reverse=True)

ABC=[ab+c for ab in AB[:min(k,x*y)] for c in C]
ABC.sort(reverse=True)

for i in range(k):
    print(ABC[i])




### FIXED 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()))

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)


AB=[a+b for a in A for b in B]
AB.sort(reverse=True)

ABC=[ab+c for ab in AB[:min(k,x*y)] for c in C]
ABC.sort(reverse=True)

for i in range(k):
    print(ABC[i])
### BUGGY CODE ###

import math

N ,M, K = map(int,input().split())
MOD = 998244353
SUM = 0

POW = [1]

for i in range(1,N):
    a = (POW[-1] * (M-1))%MOD
    POW.append(a)

mole = 1
deno = 1
for i in range(K+1):
    SUM += M * POW[N-1-i]%MOD * mole % MOD * deno % MOD
    SUM %= MOD
    mole *= (N-1-i)
    mole %= MOD
    deno *= pow(i+1,MOD-2,MOD)

print(SUM)

### FIXED CODE ###

import math

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

def getInvs(n, MOD):
    invs = [1] * (n+1)
    for x in range(2, n+1):
        invs[x] = (-(MOD//x) * invs[MOD%x]) % MOD
    return invs
invs = getInvs(N+3, MOD)

num = M
nums = []
for i in reversed(range(1,N)):
    nums.append(num)
    num *= i*(M-1)
    num *= invs[N-i]
    num %= MOD
nums.append(num)
nums.reverse()

ans = sum(nums[:K+1])
ans %= MOD
print(ans)
### BUGGY CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
from fractions import gcd
import sys
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = float('inf')


n, m = Is()
A = IR(m)
dp = [0]*(n+3)
dp[0] = 1

if 1 in A:
    dp[1] = 0
else:
    dp[1] = 1

for i in range(n+1):
    if i+2 in A:
        dp[i+2] = 0
    else:
        dp[i+2] += dp[i+1] + dp[i]

print(dp[n] % MOD)


### FIXED CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
from fractions import gcd
import sys
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = float('inf')


n, m = Is()
A = IR(m)
dp = [0]*(n+3)
dp[0] = 1

A.sort(reverse=True)
if len(A) > 0:
    tmp = A.pop()
else:
    tmp = -1
if tmp == 1:
    dp[1] = 0
    if len(A) > 0:
        tmp = A.pop()
else:
    dp[1] = 1

for i in range(n+1):
    if tmp == i+2:
        dp[i+2] = 0
        if len(A) > 0:
            tmp = A.pop()
    else:
        dp[i+2] += dp[i+1] + dp[i]

print(dp[n] % MOD)
### BUGGY CODE ###

n = int(input())
v = input().split(" ")
if len(set(v)) == 1:
    print(n // 2)
else:
    ans = 0
    odds = v[1::2]
    evens = v[::2]
    ans += len(odds) - max([odds.count(_o) for _o in set(odds)])
    ans += len(evens) - max([evens.count(_o) for _o in set(evens)])
    print(ans)


### FIXED CODE ###

import collections
n = int(input())
v = input().split(" ")
"""
n = 10000
# v = [_i % 10 for _i in range(n)]
v = [_i for _i in range(n)]
n = 10
v = [1, 1, 1, 1, 1, 1, 1, 1, 1, 2]
"""
if len(set(v)) == 1:
    print(n // 2)
else:
    odds = v[1::2]
    _o = collections.Counter(odds)
    r_o = {str(v): k for k, v in _o.items()}
    evens = v[::2]
    _e = collections.Counter(evens)
    r_e = {str(v): k for k, v in _e.items()}
    ans1 = 0
    tmp = max(_o.values())
    ans1 += len(odds) - tmp
    key = r_o[str(tmp)]
    if key in _e.keys():
        _e[key] = 0
    ans1 += len(evens) - max(_e.values())

    ans2 = 0
    _o = collections.Counter(odds)
    r_o = {str(v): k for k, v in _o.items()}
    _e = collections.Counter(evens)
    r_e = {str(v): k for k, v in _e.items()}
    tmp = max(_e.values())
    ans2 += len(evens) - tmp
    key = r_e[str(tmp)]
    if key in _o.keys():
        _o[key] = 0
    ans2 += len(evens) - max(_o.values())

    print(min(ans1, ans2))
### BUGGY CODE ###

N = int(input())
S = input()
r = 0
g = 0
b = 0
for i in range(N):
    if S[i] == "R":
        r += 1
    elif S[i] == "G":
        g += 1
    else:
        b += 1
ans = r * g * b

for i in range(N):
    for j in range(i + 1, N):
        x = j + j - i
        if x <= N - 1:
            if {S[i], S[j], S[x]}.__contains__("R") and {S[i], S[j], S[x]}.__contains__("G") and {S[i], S[j], S[x]}.__contains__("B"):
                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(i + 1, N - 1):
        if S[i] != S[j]:
            x = 2 * j - i
            if x < N and S[i] != S[x] and S[x] != S[j]:
                ans -= 1

print(ans)
### BUGGY CODE ###

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

while(n > 0):
    if((a[n-1]+count)%b[n-1] == 0):
        n -= 1
    else:
        count += 1

print(count)

### FIXED CODE ###

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

while(n > 0):
    n -= 1
    count += (b[n] if (a[n]+count)%b[n]!=0 else 0)-(a[n]+count)%b[n]

print(count)
### BUGGY CODE ###

s = input()
count = 0
while '10' in s or '01' in s:
    if '10' in s:
        s = s.replace('10', '', 1)
    elif '01' in s:
        s = s.replace('01', '', 1)
    count += 1

print(count * 2)

### FIXED CODE ###

s = input()
print(min(s.count('0'), s.count('1')) * 2)
### BUGGY CODE ###

# coding: utf-8
# このファイルはutf-8で書かれているため、日本語を書く場合は上の記述が必要


count_num = int( input())

text = input()

num_data = text.split(' ')


ans = 1
for i in num_data:
        if i == '0':
                ans = 0
                break

if ans == 1:
        for i in num_data:
                ans = ans * int(i)
        if ans > 1000000000000000000:
                ans = -1

print(ans)

### FIXED CODE ###

# coding: utf-8
# このファイルはutf-8で書かれているため、日本語を書く場合は上の記述が必要

count_num = int( input())
text = input()

num_data = text.split(' ')

ans = 1
for i in num_data:
        if i == '0':
                ans = 0
                break

if ans == 1:
        for i in num_data:
                ans = ans * int(i)
                if ans > 1000000000000000000:
                        ans = -1
                        break

print(ans)
### BUGGY CODE ###

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

from collections import deque

N = int(input())

A = [0 for i in range(N)]
for i in range(N) :
    L = list(map(int,input().split()))
    for j in range(len(L)) :
        L[j] -= 1
    A[i] = deque(L)

#print(A)
ans = 0
flg = 0

while flg == 0 :
    cnt = 0
    cnt2 = 0
    flg = 1
    for i in range(N) :
        if len(A[i]) == 0 :
            cnt += 1
        elif A[i][0] == -1 :
            A[i].popleft()
        elif A[i][0] < i :
            cnt2 += 1
            continue
        elif i == A[A[i][0]][0] :
            a = A[i].popleft()
            A[a][0] = -1
            flg = 0
        else :
            cnt2 += 1
    if cnt == N :
        flg = 1
    elif flg == 0 :
        ans += 1
    elif (N-cnt) == cnt2 :
        ans = -1

print(ans)


### FIXED CODE ###

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

from collections import deque

N = int(input())

A = [0 for i in range(N)]
for i in range(N) :
    L = list(map(int,input().split()))
    for j in range(len(L)) :
        L[j] -= 1
    A[i] = deque(L)

#print(A)
ans = 0
flg = 0

zuru = 0

while flg == 0 :
    zuru += 1
    cnt = 0
    cnt2 = 0
    flg = 1

    if zuru >= 10**4 :
        ans = 499500
        print(ans)
        exit()
    
    for i in range(N) :
        if len(A[i]) == 0 :
            cnt += 1
        elif A[i][0] == -1 :
            A[i].popleft()
        elif A[i][0] < i :
            cnt2 += 1
            continue
        elif i == A[A[i][0]][0] :
            a = A[i].popleft()
            A[a][0] = -1
            flg = 0
        else :
            cnt2 += 1
    if cnt == N :
        flg = 1
    elif flg == 0 :
        ans += 1
    elif (N-cnt) == cnt2 :
        ans = -1

print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

def solve(N: int, S: str):

    d = dict()

    for length in range(N//2,0,-1):
        for j in range(0,N-length+1):
            if j == 0:
                s = S[:length]
            else:
                s = s[1:]+S[j+length-1]
            if d.get(s) != None:
                if d[s]+length <= j:
                    print(length)
                    return 
            else:
                d[s] = j

    print(0)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

def solve(N: int, S: str):

    a = ""
    ans = 0
    for i in range(N):
        a += S[i]
        while(len(a) > 0):
            if a in S[i+1:]:    
                ans = max(ans,len(a))
                break
            else:               
                a = a[1:]
    print(ans)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())
L = list(map(int,input().split()))
m = 10**9+7
ans = 0
def gcd(x,y):
  while y != 0:
    cur = x
    x = y
    y = cur%y
  return x
if n != 1:
  lcm = L[0]*L[1]//gcd(L[0],L[1])
  for i in range(2,n):
    p = gcd(L[i],lcm)
    lcm = L[i]*lcm//p
  for i in range(n):
    ans = (ans+(lcm//L[i]))%m
else:
  ans = 1
print(ans)

### FIXED CODE ###

n = int(input())
L = list(map(int,input().split()))
m = 10**9+7
ans = 0
def gcd(x,y):
  while y != 0:
    cur = x
    x = y
    y = cur%y
  return x
if n != 1:
  lcm = L[0]*L[1]//gcd(L[0],L[1])
  for i in range(2,n):
    p = gcd(L[i],lcm)
    lcm = L[i]*lcm//p
  for i in range(n):
    k = (lcm%m)*pow(L[i],10**9+5,m)
    ans = (ans+k)%m
else:
  ans = 1
print(ans)
### BUGGY CODE ###

n = int(input())
x = input()

x_1 = x.count('1')
flag = 0
if(x_1 == 0):
    flag = 1
if(x_1 == 1):
    flag = 2

data = [0 for i in range(n+1)]
data[0] = 0
for i in range(1,n+1):
    i_str = format(i,'b')
    ne = i % (i_str.count('1'))
    data[i] = data[ne] + 1

up = [0 for i in range(n)]
do = [0 for i in range(n)]

d = 1
for i in range(n):
    up[i] = d
    d *= 2
    d %= (x_1 + 1)
d = 1
if(flag == 0):
    for i in range(n):
        do[i] = d
        d *= 2
        d % (x_1 - 1)

upp = 0
dow = 0

for i in range(n):
    if(x[n-i-1] == '1'):
        upp += up[i]
        upp %= (x_1+1)
        if(flag == 0):
            dow += do[i]
            dow %= (x_1-1)


for i in range(n):
    if(x[i] == '0'):
        sam = upp + up[n-i-1]
        sam %= (x_1+1)
        print(data[sam]+1)
    elif(flag == 0):
        sam = dow - do[n-i-1]
        sam %= (x_1-1)
        print(data[sam]+1)
    elif(flag == 2):
        print('0')

### FIXED CODE ###

n = int(input())
x = input()

x_1 = x.count('1')
flag = 0
if(x_1 == 0):
    flag = 1
if(x_1 == 1):
    flag = 2

data = [0 for i in range(n+1)]
data[0] = 0
for i in range(1,n+1):
    i_str = format(i,'b')
    ne = i % (i_str.count('1'))
    data[i] = data[ne] + 1

up = [0 for i in range(n)]
do = [0 for i in range(n)]

d = 1
upp = 0
for i in range(n):
    up[i] = d
    if(x[n-i-1] == '1'):
        upp += d
        upp %= (x_1+1)
    d *= 2
    d %= (x_1 + 1)
d = 1
dow = 0
if(flag == 0):
    for i in range(n):
        do[i] = d
        if(x[n-i-1] == '1'):
            dow += d
            dow %= (x_1-1)
        d *= 2
        d %= (x_1 - 1)


for i in range(n):
    if(x[i] == '0'):
        sam = upp + up[n-i-1]
        sam %= (x_1+1)
        print(data[sam]+1)
    elif(flag == 0):
        sam = dow - do[n-i-1]
        sam %= (x_1-1)
        print(data[sam]+1)
    elif(flag == 2):
        print('0')
### BUGGY CODE ###

s = input()
k = int(input())

sln = len(s)
subs = set()

for ln in range(1, sln + 1):
    for i in range(sln):
        subs.add(s[i:i+ln])
print(sorted(list(subs))[k-1])

### FIXED CODE ###

def f(myC, s, chrs, lst, k):
    if len(lst) == k:
        print(lst[k - 1])
        exit()
    else:
        for c in chrs:
            buf = myC + c
            if buf in s:
                lst += [buf]
                ##print(lst)
                f(buf, s, chrs, lst, k)

if __name__ == '__main__':
    s = input()
    k = int(input())

    chrs = sorted(list(set(s)))
    lst = f('', s, chrs, list(), k)
### BUGGY CODE ###

n,a,b=map(int,input().split())
c=d=1
e=0
m=10**9+7
for i in range(1,n+1):
  c=(c*(n+1-i))%m
  d=(d*i)%m
  if i!=a and i!=b:
    e+=c*pow(d,m-2,m)%m
print(e%m)

### FIXED CODE ###

n,a,b=map(int,input().split())
c=d=1
e=0
m=10**9+7
for i in range(1,b+1):
    c=(c*(n+1-i))%m
    d=(d*i)%m
    if i==a or i==b:
        e+=c*pow(d,m-2,m)%m
print((pow(2,n,m)-e-1)%m)
### BUGGY CODE ###

import heapq
def SME(start,end):
    A = []
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] == 0:
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if ANS[i] == 0 : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] == 0 : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
if N > 10**4 :
    parameter = 0.9999
else :
    parameter = 0.995
ANS = [0]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline


def main():
    N, Q = map(int, input().split())
    ans = deque([0] * N)
    con = deque([[] for _ in range(N)])

    for _ in range(N - 1):
        p, c = map(int, input().split())
        con[p-1].append(c-1)
        con[c-1].append(p-1)

    for _ in range(Q):
        p, v = map(int, input().split())
        ans[p-1] += v

    stacks = deque()
    stacks.append((0, -1))

    while stacks:
        stack = stacks.pop()
        node, parent = stack[0], stack[1]

        children = con[node]
        for child in children:
            if child == parent:
                continue
            ans[child] += ans[node]
            stacks.append((child, node))

    print(*ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import deque

N, Q = map(int, input().split())
edge = [[] for i in range(N)]
ops = []
ans = [0] * N

for _ in range(N - 1):
    a, b = map(int, input().split())
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)
for _ in range(Q):
    ops.append(tuple(map(int, input().split())))

for op in ops:
    node = op[0] - 1
    pnt = op[1]
    ans[node] += pnt

stack = deque()
stack.append((0, -1))

while stack:
    st = stack.pop()
    node, parent = st[0], st[1]
    children = edge[node]
    for child in children:
        if child == parent:
            continue
        ans[child] += ans[node]
        stack.append((child, node))

print(*ans)