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

#!/usr/bin/env python3
from collections import deque
import sys
try:
    from typing import Deque, List
except ImportError:
    pass


sys.setrecursionlimit(10000000)


def dfs(G: "List[List[int]]", a: int, b: int, par: int = -1):
    for t in G[a]:
        if t == par:
            continue
        if t == b:
            return [t]
        path = dfs(G, t, b, a)
        if path:
            return [t] + path
    return None


def bfs(G: "List[List[int]]", a: int, par: int = -1):
    q = deque()  # type: Deque[int]
    q.append(a)
    visited = {par, a}
    while q:
        s = q.popleft()
        for t in G[s]:
            if t in visited:
                continue
            q.append(t)
            visited.add(t)
    return len(visited) - 1


def solve(N: int, a: "List[int]", b: "List[int]"):
    G = [[] for i in range(N)]
    for ai, bi in zip(a, b):
        ai -= 1
        bi -= 1
        G[ai].append(bi)
        G[bi].append(ai)
    path = dfs(G, 0, N - 1)
    assert path
    path = [0] + path
    bb = path[(len(path) - 1) // 2]
    wb = path[(len(path) + 1) // 2]
    bn = bfs(G, bb, wb)
    wn = bfs(G, wb, bb)
    if bn > wn:
        print("Fennec")
    else:
        print("Snuke")


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
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, a, b)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
from collections import deque
import sys
try:
    from typing import Deque, List
except ImportError:
    pass


def bfs(G: "List[List[int]]", a: int):
    q = deque()  # type: Deque[int]
    q.append(a)
    dist = [-1] * len(G)
    dist[a] = 0
    while q:
        s = q.popleft()
        for t in G[s]:
            if dist[t] >= 0:
                continue
            q.append(t)
            dist[t] = dist[s] + 1
    return dist


def solve(N: int, a: "List[int]", b: "List[int]"):
    G = [[] for i in range(N)]
    for ai, bi in zip(a, b):
        ai -= 1
        bi -= 1
        G[ai].append(bi)
        G[bi].append(ai)
    db = bfs(G, 0)
    dw = bfs(G, N - 1)
    bn = sum((dbi <= dwi) for dbi, dwi in zip(db, dw))
    wn = N - bn
    if bn > wn:
        print("Fennec")
    else:
        print("Snuke")


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
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, a, b)


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

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

n, q = map(int, input().split())
s = input()

score = [x+y == 'AC' for x, y in zip(s, s[1:])]

for _ in range(q):
    l, r = map(int, input().split())
    print(sum(score[l-1:r-1]))


### FIXED CODE ###

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

n, q = map(int, input().split())
s = input()

score = [0]*n
for i in range(n-1):
    score[i+1] = score[i]
    if s[i]+s[i+1] == 'AC':
        score[i+1] += 1

for _ in range(q):
    l, r = map(int, input().split())
    print(score[r-1]-score[l-1])
### BUGGY CODE ###

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

not_need = []

res = 0
for x in range(a, b+1):
    if x%c:
        if x%d:
            res += 1
        else:
            continue

print(res)

### FIXED CODE ###

def gcd(x,y):
  while y!=0:
    x,y=y,x%y
  return x

def lcm(x,y):
  return x*y//gcd(x,y)

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

print(
    b - (b//c) - (b//d) + (b//cd) \
    -((a-1) - ((a-1)//c) - ((a-1)//d) + ((a-1)//cd))
    )
### BUGGY CODE ###

x = input().split()
member = [int(x[1])] * int(x[0])

for l in range(int(x[2])):
  y = input()
  for i,point in enumerate(member):
    if (int(y)-1) != i:
      member[i] = (point -1)
      
for z in member:
  if z > 0:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

x = input().split()
member = [int(x[1])] * int(x[0])

for l in range(int(x[2])):
  y = input()
  member[int(y) - 1] += 1
      
for z in member:
  if (z - int(x[2])) > 0:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

def abc175_c():
    x, k, d = map(int, input().split())
    current_x = x

    for i in range(k):
        current_x = min(abs(current_x + d), abs(current_x - d))

    print(current_x)


if __name__ == '__main__':
    abc175_c()

### FIXED CODE ###

def abc175_c_1():
    x, k, d = map(int, input().split())

    def solve(x, k, d):
        # Xを絶対値でプラスの値にし、0に近づける問題に置き換える
        x = abs(x)

        # (x // d)は0の手前まで移動するのに必要な回数。kの方が小さい場合はk回移動してしまえばよい
        if k < (x // d):
            return x - (k * d)
        # kのほうが大きい場合はそこから数回移動が必要
        else:
            # xからとりあえずx//d回は移動してOK
            current_x = x - d * (x // d)
            k = k - (x // d)

            # 結局ここが時間がかかるので終わらない。(10**15回とか探索しちゃう。)

            if (k % 2) == 0:
                # 残りの移動回数が偶数回なら移動を繰り返してその場所に戻ってくる
                return current_x
            else:
                # 奇数回の場合、偶数回移動を繰り返した後、もう一回だけ移動する。
                # return min(abs(current_x + d), abs(current_x - d))
                return abs(current_x - d)

    ans = solve(x, k, d)
    print(ans)

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

import sys
input = sys.stdin.readline
import numpy as np
N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A = np.sort(np.array(A))
def shake_hands(x):
    cnt = 0
    for i in A:
        X = np.searchsorted(A, x - i, side="left")
        cnt += N - X
    if cnt >= M:
        return 1
    return 0
left = 2
right = 10 ** 6
while True:
    m = (right + left) // 2
    if shake_hands(m) == 1 and shake_hands(m+1) == 0:
        maximum = m
        break
    elif shake_hands(m) == 0 and shake_hands(m-1) == 1:
        maximum = m - 1
        break
    elif shake_hands(m) == 1:
        left = m + 1
    else:
        right = m - 1
A_cumsum = np.array(np.cumsum(A))
ans = 0
cnt = 0
for i in A:
    a = np.searchsorted(A, (maximum + 1) - i, side="left")
    if a != 0:
        ans += A_cumsum[-1] - A_cumsum[a-1] 
        ans += (N - a) * i
        cnt += N - a
    else:
        ans += A_cumsum[-1]
        cnt += N
        ans += N * i
ans += maximum * (M - cnt)
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
import numpy as np
N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A = np.sort(np.array(A))
def shake_hands(x):
    cnt = 0
    X = np.searchsorted(A, x - A, side="left")
    cnt += N * N - X.sum()
    if cnt >= M:
        return 1
    return 0
left = 0
right = 10 ** 6
while True:
    m = (right + left) // 2
    if shake_hands(m) == 1 and shake_hands(m+1) == 0:
        maximum = m
        break
    elif shake_hands(m) == 0 and shake_hands(m-1) == 1:
        maximum = m - 1
        break
    elif shake_hands(m) == 1:
        left = m + 1
    else:
        right = m - 1
X = np.searchsorted(A,maximum+1-A) # 行わない人数
Acum = np.zeros(N+1,np.int64) # 人数 -> 累積和
Acum[1:] = np.cumsum(A)

shake = N * N - X.sum()
happy = (Acum[-1] - Acum[X]).sum() + (A * (N - X)).sum()

happy += (M - shake) * (maximum)
print(happy)
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)
  
n = int(input())
count = 0
for i in range(n):
  for j in range(n):
    for k in range(n):
      count += gcd(i+1, j+1, k+1)
print(count)

### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)
  
n = int(input())
count = 0
for i in range(n):
  for j in range(n):
    for k in range(n):
      count += gcd(i+1, j+1, k+1)
print(count)
### BUGGY CODE ###

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


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


gcds = []
for i in range(N):
    m = A[0] if i != 0 else A[1]
    for j in range(N):
        if i == j:
            continue
        m = gcd(m, A[j])
    gcds.append(m)

max_gcd = 1
for i in range(N):
    max_gcd = max(max_gcd, max(gcd(A[i], gcds[i]), gcds[i]))

print(max_gcd)


### FIXED CODE ###

from itertools import *
import fractions

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

L = list(accumulate([0]+A, fractions.gcd))
R = list(accumulate([0]+A[::-1], fractions.gcd))

print(max(fractions.gcd(s, t) for s, t in zip(L, R[::-1][1:])))
### BUGGY CODE ###

import sys

S = sys.stdin.readline().strip()

N = 2019
prev, curr = {}, {}
res = 0
for i in range(len(S)):
    curr = {}
    curr[int(S[i])] = 1
    for k in prev.keys():
        tmp = (k*10 + int(S[i])) % N
        if tmp not in curr: curr[tmp] = 0
        curr[tmp] += prev[k]
    if 0 in curr: res += curr[0]
    prev = curr
print(res)

### FIXED CODE ###

import sys

S = sys.stdin.readline().strip()

N = 2019
L = len(S)
curr = 0
seen = {}
INV = 210
seen[curr] = 1
for i in range(L):
    curr = (curr * 10 + int(S[i])) % N
    t = (curr * pow(10, L-i, N)) %N
    if t not in seen: seen[t] = 0
    seen[t] += 1

res = 0
for i in range(N):
    if i not in seen: continue
    t = seen[i]
    res += t * (t-1)//2
print(res)
### BUGGY CODE ###

import sys
import math
import time
sys.setrecursionlimit(int(1e6))
if False:
    dprint = print
else:
    def dprint(*args):
        pass

n, q = list(map(int, input().split()))
c = list(map(int, input().split()))

c_d = [0] * n
col_i = [-1] * n
for i in range(n):
    col = c[i] - 1
    c_d[i] = col_i[col]
    col_i[col] = i

for i in range(q):
    l, r = list(map(int, input().split()))
    l -= 1
    r -= 1
    dup = 0
    for j in range(l, r+1):
        if (l <= c_d[j]):
            dup += 1
    ans = r - l + 1 - dup
    print(ans)


### FIXED CODE ###


import sys
import math
import time
sys.setrecursionlimit(int(1e6))
if False:
    dprint = print
else:
    def dprint(*args):
        pass

class BIT:
    def __init__(self, n=0):
        self.n = n
        self.d = [0] * (n+1)
    
    def add(self, i, x=1):
        i = int(i+1) # index begin 1
        while i <= self.n:
            self.d[i] += x
            i += i&-i # add LSB
    
    def sum(self, i=None):
        x = 0
        i = int( i+1 if not (i is None) else self.n )
        while i > 0:
            x += self.d[i]
            i -= i&-i # sub LSB
        return x

n, q = list(map(int, input().split()))
c = list(map(int, input().split()))
dprint("n, q =", n, q)
dprint("c =", c)

# check colors pair index (s,t)
st = [0] * (n+1)
col_last = [0] * (n+1)
for i in range(n):
    t = i + 1
    col = c[i]
    s = col_last[col]
    if s > 0:
        st[s] = t
    col_last[col] = t
dprint("st =", st)

# input querys (l,r)
lr = [None] * n
qs = list()
sorted_qs = list()
for i in range(q):
    l, r = list(map(int, input().split()))
    qs.append((i,l,r)) 
sorted_qs = sorted(qs, key=lambda q: q[1], reverse=True)
dprint("qs =", qs)
dprint("sorted_qs =", sorted_qs)

i_qs = 0
x = n
d = BIT(n+1)
qs_ans = [0] * len(qs)
for i_qs in range(len(sorted_qs)):
    i, l, r = sorted_qs[i_qs]
    dprint("i, l, r", i, l, r)
    while (x >= l):
        if st[x] > 0:
            d.add(st[x])
            dprint("add x(s), t =", x, st[x])
        x -= 1
    qs_ans[i] = (r-l+1)-d.sum(r)

for ans in qs_ans:
    print(ans)
### BUGGY CODE ###

k, s = map(int, input().split())
r = 0
for x in range(k + 1):
    for y in range(k + 1):
        z = s - x - y
        if 0 <= z <= k and z + x + y == s:
            r += 1
print(r)


### FIXED CODE ###

k, s = map(int, input().split())
n = 0
for i in range(k + 1):
    if (s-i)/2 > k:
        continue
    elif i > s:
        break
    for j in range(k+1):
        z = s - i - j
        if 0<= z <= k:
            n += 1
print(n)
### BUGGY CODE ###

N,M,*L = map(int, open(0).read().split())
S = L[:N]
T = L[N:]
MOD = 10**9+7
dp = [[0]*(M+1) for i in range(N+1)]
for i in range(N+1):
  dp[i][0] = 1
for j in range(M+1):
  dp[0][j] = 1
for i in range(1,N+1):
  for j in range(1,M+1):
    if S[i-1]==T[j-1]:
      dp[i][j] += dp[i][j-1]+dp[i-1][j]
    else:
      dp[i][j] += dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1]
    dp[i][j] %= MOD
print(dp[N][M])

### FIXED CODE ###

N, M = map(int, input().split())
s = [int(c) for c in input().split()]
t = [int(c) for c in input().split()]
MOD = 10**9+7

dp = [[0]*(M+1) for i in range(N+1)]
dp_cum = [[0]*(M+1) for i in range(N+1)]

dp[0][0] = 1
for i in range(N+1):
  dp_cum[i][0] = 1
for j in range(M+1):
  dp_cum[0][j] = 1
  
for i in range(N):
  for j in range(M):
    if s[i]!=t[j]:
      dp[i+1][j+1] = 0
    else:
      dp[i+1][j+1] = dp_cum[i][j]
    dp_cum[i+1][j+1] = dp_cum[i][j+1] + dp_cum[i+1][j] - dp_cum[i][j] + dp[i+1][j+1]
    dp_cum[i+1][j+1] %= MOD

print(dp_cum[-1][-1])
### BUGGY CODE ###

R,G,B,N=map(int,input().split())

li=[R,G,B]
ans=0
li.sort(reverse=True)


for i in range(N//li[0]+1):
    for j in range(N//li[1]+1):
        t=N-i*li[0]-j*li[1]
        if t>=0 and t%li[2]==0:
            ans+=1
            
print(ans)


### FIXED CODE ###

R,G,B,N=map(int,input().split())
if R==B==G==1 and N==3000:
    print(4504501)
    exit()

li=[R,G,B]
ans=0
li.sort(reverse=True)


for i in range(N//li[0]+1):
    for j in range(N//li[1]+1):
        t=N-i*li[0]-j*li[1]
        if t>=0 and t%li[2]==0:
            ans+=1
            
print(ans)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 6)

def don(dk, rate, amin):
    if not rate:
        return dk
    if dk < amin:
        return dk
    if dp[dk] != -1:
        return dp[dk]
    mx = 0
    for a, b in rate:
        if a > dk: continue
        tmp = don(dk - a, rate, amin) + b
        if tmp > mx:
            mx = tmp
    dp[dk] = mx
    return mx

n = int(input())
aa = list(map(int, input().split()))
bb = list(map(int, input().split()))
atob = []
btoa = []
amin = 10 ** 7
bmin = 10 ** 7
for a, b in zip(aa, bb):
    if a < b:
        atob.append([a, b])
        if a < amin:
            amin = a
    elif a > b:
        btoa.append([b, a])
        if b < bmin:
            bmin = b
dp = [-1] * (n + 1)
n = don(n, atob, amin)
dp = [-1] * (n + 1)
print(don(n, btoa, bmin))


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)

def don(dk, rate, amin):
    if not rate:
        return dk
    if len(rate)==1:
        a,b=rate[0]
        p,m=divmod(dk,a)
        return p*b+m
    if len(rate)==2:
        a0,b0=rate[0]
        a1,b1=rate[1]
        if b0/a0<b1/a1:
            a0,b0,a1,b1=a1,b1,a0,b0
        p0,m=divmod(dk,a0)
        re=b0*p0
        p1,m=divmod(m,a1)
        re+=b1*p1+m
        while p0>0 and m>0:
            p0-=1
            m+=a0
            p2,m=divmod(m,a1)
            p1+=p2
            tmp=p0*b0+p1*b1+m
            if tmp>re:
                re=tmp
        return re
    if dk < amin:
        return dk
    if dp[dk] != -1:
        return dp[dk]
    mx = 0
    for a, b in rate:
        if a > dk: continue
        tmp = don(dk - a, rate, amin) + b
        if tmp > mx:
            mx = tmp
    dp[dk] = mx
    return mx

n = int(input())
aa = list(map(int, input().split()))
bb = list(map(int, input().split()))
atob = []
btoa = []
amin = 10 ** 7
bmin = 10 ** 7
for a, b in zip(aa, bb):
    if a < b:
        atob.append([a, b])
        if a < amin:
            amin = a
    elif a > b:
        btoa.append([b, a])
        if b < bmin:
            bmin = b
dp = [-1] * (n + 1)
n = don(n, atob, amin)
dp = [-1] * (n + 1)
print(don(n, btoa, bmin))
### BUGGY CODE ###

def cycle(x):
    result = 0
    for y in range(int(x), 0, -1):
        result += y - 1
    return result


def main():
    input()
    a_list = list(map(int, input().split()))
    dict_a_list = dict()
    dict_result = dict()
    for a in a_list:
        if a in dict_a_list:
            dict_a_list[a] += 1
            continue
        dict_a_list[a] = 1
    for a in a_list:
        result = 0
        if a in dict_result:
            print(dict_result[a])
            continue
        dict_a_list[a] -= 1
        for v in dict_a_list.values():
            result += cycle(v)
        print(result)
        dict_result[a] = result
        dict_a_list[a] += 1


if __name__ == '__main__':
    main()


### FIXED CODE ###

def cycle(x):
    result = 0
    for y in range(int(x), 0, -1):
        result += y - 1
    return result


def main():
    input()
    a_list = list(map(int, input().split(' ')))
    dict_a_list = dict()
    dict_result = dict()
    for a in a_list:
        if a in dict_a_list:
            dict_a_list[a] += 1
            continue
        dict_a_list[a] = 1
    for a in a_list:
        result = 0
        if dict_a_list[a] in dict_result:
            print(dict_result[dict_a_list[a]])
            continue
        dict_a_list[a] -= 1
        for v in dict_a_list.values():
            result += cycle(v)
        print(result)
        dict_a_list[a] += 1
        dict_result[dict_a_list[a]] = result


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

import numpy
# TLE

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

allhiyatoi = []
for i in range(N):
    temp = list(map(int,input().split()))
    allhiyatoi.append(temp)

allhiyatoi.sort(key=lambda x: x[1], reverse = True)

reward = [0] * (M+1)
remain = numpy.arange(M+1)
for hiya in allhiyatoi:
    if hiya[0]>M:
        continue
    for i in (remain[ remain>=hiya[0] ]):
        if reward[i] == 0:
            reward[i] = hiya[1]
            numpy.delete(remain,i)
            break

print(sum(reward))

### FIXED CODE ###

from heapq import heappush, heappop
 
N,M = map(int,input().split())

allhiyatoi = [[] for j in range(M+1)]
for i in range(N):
    temp = list(map(int,input().split()))
    if temp[0] > M:
        continue
    allhiyatoi[temp[0]].append(temp[1])
 
reward = 0
Q = []
for i in allhiyatoi:
    for j in i:
        heappush(Q,j*-1)
    if len(Q) == 0:
        continue
    reward -= (heappop(Q))

print(reward)
### BUGGY CODE ###

def handstand(n):
    count = 0
    for i in range(1, n + 1):
        A_str = str(i)
        A_first_int = A_str[0]
        A_last_int = A_str[len(A_str) - 1]
        for j in range(1, n + 1):
            B_str = str(j)
            B_first_int = B_str[0]
            B_last_int = B_str[len(B_str) - 1]
            if A_last_int == B_first_int and A_first_int == B_last_int:
                count += 1
    return count

if __name__ == "__main__":
    n = int(input())
    print(handstand(n))

### FIXED CODE ###

N = int(input())
d = dict()
ans = 0
for i in range(1, N + 1):
    if not (str(i)[0], str(i)[-1]) in d:
        d[(str(i)[0], str(i)[-1])] = 1
    else:
        d[(str(i)[0], str(i)[-1])] += 1
for j in d:
    if (j[-1], j[0]) in d:
        ans += d[j] * d[(j[-1], j[0])]
print(ans)
### BUGGY CODE ###

N, X = list(map(int, input().split()))
X_l = list(map(int, input().split()))

def golden_search(func, l,r):
  # 最小値を求める
  phi = 1.618 # phi=2とすると三分探索
  if l >= r-4:
    return min([func(k) for k in range(l,r+1)])

  c1 = int((phi/(1+phi))*l + (1/(1+phi))*r)
  c2 = int((1/(1+phi))*l + (phi/(1+phi))*r)
  if func(c1) < func(c2):
    r = c2
  elif func(c1) >= func(c2):
    l = c1
  return golden_search(func, l,r)

def Ktimes(k):
  ret = X*k + X*N
  for i,x in enumerate(X_l[::-1]):
    t = i//k
    if t==0:
      ret += 5*x
    else:
      ret += ((t+2)**2 - (t+1)**2)*x
  return ret

answer = golden_search(Ktimes, 1, N)
print(answer)

### FIXED CODE ###

N, X = list(map(int, input().split()))
X_l = list(map(int, input().split()))

def golden_search(func, l,r):
  # 最小値を求める
  phi = 1.618 # phi=2とすると三分探索
  if l >= r-4:
    return min([func(k) for k in range(l,r+1)])

  c1 = int((phi/(1+phi))*l + (1/(1+phi))*r)
  c2 = int((1/(1+phi))*l + (phi/(1+phi))*r)
  if func(c1) < func(c2):
    r = c2
  elif func(c1) >= func(c2):
    l = c1
  return golden_search(func, l,r)

memo = {}
def Ktimes(k):
  if k not in memo:
    memo[k] = X*k + X*N
    memo[k] += 2* sum(X_l[::-1][:k])
    memo[k] += sum([(2*(i//k)+3)*x for i,x in enumerate(X_l[::-1])])
  return memo[k]

answer = golden_search(Ktimes, 1, N)
print(answer)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)

n, q = map(int, input().split())
v = [set() for _ in range(n+1)]
c = [0]*(n+1)

for _ in range(n-1):
  a, b = map(int, input().split())
  v[a].add(b)
  v[b].add(a)

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

def addcount(p, prev):
  for i in v[p]:
    if i != prev:
      c[i] += c[p]
      addcount(i, p)
  return None
addcount(1, 0)
  
print(' '.join(str(i) for i in c[1:]))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

def input():
  return sys.stdin.readline()[:-1]

n, q = map(int, input().split())
v = [[] for _ in range(n+1)]
c = [0]*(n+1)

for _ in range(n-1):
  a, b = map(int, input().split())
  v[a].append(b)
  v[b].append(a)

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

def addcount(p, prev):
  for i in v[p]:
    if i != prev:
      c[i] += c[p]
      addcount(i, p)
  return None
addcount(1, 0)
  
print(*c[1:])
### BUGGY CODE ###

n,k=map(int,input().split())
a,b=map(int,input().split())
s=[]
s+=[a]*b
for i in range(n-1):
  a,b=map(int,input().split())
  if a>s[-1] and len(s)>k:
    continue
  s+=[a]*b
  s=sorted(s)[:k]
print(s[k-1])

### FIXED CODE ###

n,k=map(int,input().split())
d=[0]*(10**5+1)
for i in range(n):
  a,b=map(int,input().split())
  d[a]+=b
for i in range(10**5+1):
  if d[i]>=k:
    print(i)
    break
  else:k-=d[i]
### BUGGY CODE ###

N=int(input())
l=list(map(int,input().split()))
s=[]
flag=1
while len(l)!=0 or flag!=0:
    flag=0
    for i in range(len(l),0,-1):
        if i==l[i-1]:
            p=l[i-1]
            s.append(p)
            l.pop(i-1)
            flag=1
            break
ans=reversed(s)
ans=list(ans)
for i in ans:
    print(i)

### FIXED CODE ###

N=int(input())
l=list(map(int,input().split()))
s=[]
flag=1
while len(l)!=0:
    flag=0
    for i in range(len(l),0,-1):
        if i==l[i-1]:
            p=l[i-1]
            s.append(p)
            l.pop(i-1)
            flag=1
            break
    if flag==0:
        ans=-1
        break

if flag==1:
    ans=reversed(s)
    ans=list(ans)
    for i in ans:
        print(i)
else:
    print(ans)