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

n = int(input())
s = [input() for i in range(n)]
ans = []
out = []
word_list = list(set(s))

for i in word_list:
  ans.append([s.count(i), i])

ans.sort(reverse = True)

for j in ans:
  if j[0] == ans[0][0]:
    out.append(j[1])

out.sort()
for k in out:
  print(k)


### FIXED CODE ###

from collections import Counter
n = int(input())
s = [input() for _ in range(n)]
ans = []
charctor_count = Counter(s)
max_count = max(charctor_count.values())
for k, v in charctor_count.items():
  if v == max_count:
    ans.append( k)
print("\n".join(sorted(ans)))
### BUGGY CODE ###

import sys
n = int(input())

print(0)
sys.stdout.flush()
s = input()

if s == "Vacant":
    exit()

low = 1
high = n-1
tmp = 0
cnt = 1

while low+1 < high:
    mid = (low + high) //2
    
    print(mid)
    sys.stdout.flush()
    t = input()
    cnt += 1
    
    if mid % 2 == 0:
        if t[0] == s[0]:
            low = mid
        elif t[0] == "V":
            exit()
        else:
            high = mid
    else:
        if t[0] == s[0]:
            high = mid
        elif t[0] == "V":
            exit()
        else:
            low = mid
    if cnt >= 5:
        print(s[1000])
print(high,1111)
sys.stdout.flush()
s = input()
exit()

### FIXED CODE ###

import sys
n = int(input())

print(0)
sys.stdout.flush()
s = input()

if s == "Vacant":
    exit()

low = 1
high = n-1
tmp = 0
cnt = 1

while low+1 < high:
    mid = (low + high) //2
    
    print(mid)
    sys.stdout.flush()
    t = input()
    cnt += 1
    
    if mid % 2 == 0:
        if t[0] == s[0]:
            low = mid
        elif t[0] == "V":
            exit()
        else:
            high = mid
    else:
        if t[0] == s[0]:
            high = mid
        elif t[0] == "V":
            exit()
        else:
            low = mid

print(high)
sys.stdout.flush()
s = input()
if s[0] == "V":
    exit()
else:
    print(low)
    sys.stdout.flush()
    s = input()
    exit()
### BUGGY CODE ###

import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def s(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")

s = X()
q = k()
for i in range(q):
    a = X()
    if a[0] == "1":
        s.reverse()
    else:
        if a[2] == "1":
            s.insert(0,a[4])
        else:
            s.append(a[4])

print("".join(s))


### FIXED CODE ###

import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")
al = "abcdefghijklmnopqrstuvwxyz"
AL = al.upper()

s = deque(X())
n = k()
normal = 0
for i in range(n):
  a = input().split()
  if int(a[0]) == 1:
    normal ^= 1
  else:
    k = int(a[1]) - 1
    k ^= normal
    if k == 1:
      s.append(a[2])
    else:
      s.appendleft(a[2])
print(''.join(s) if normal == 0 else ''.join(list(s)[::-1]))
### BUGGY CODE ###

from collections import deque

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

graph = [[] for i in range(N)]
dis = [["n/a"]*N for i in range(N)]

for i in range(M):
    L,R,D = map(int,input().split())
    L -= 1
    R -= 1
    graph[L].append(R)
    graph[R].append(L)
    dis[L][R] = D
    dis[R][L] = (-1)*D

data = ["n/a"]*N
det = 0

for i in range(N):
    if data[i] != "n/a":
        continue
    data[i] = 0
    stack = deque()
    stack.append(i)
    while stack:
        x = stack.pop()
        for y in graph[x]:
            if data[y] == "n/a":
                data[y] = data[x] + dis[x][y]
                stack.append(y)
            else:
                if data[y] - data[x] != dis[x][y]:
                    det = -1
                    break
    if det == -1:
        break

if det == 0:
    print("Yes")
else:
    print("No")



### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline

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

graph = [[] for i in range(N)]

for i in range(M):
    L,R,D = map(int,input().split())
    L -= 1
    R -= 1
    graph[L].append([R,D])
    graph[R].append([L,-D])
    
data = [None]*N

for i in range(N):
    if data[i] != None:
        continue
    data[i] = 0
    stack = deque()
    stack.append(i)
    while stack:
        x = stack.popleft()
        for y in graph[x]:
            if data[y[0]] == None:
                data[y[0]] = data[x] + y[1]
                stack.append(y[0])
            else:
                if data[y[0]] - data[x] != y[1]:
                    print("No")
                    sys.exit()
    
print("Yes")
### BUGGY CODE ###

N = int(input())

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

m = 1

for a in A:
    m = m * a

if m > 10**18:
    print(-1)
    exit(0)
    
print(m)

### FIXED CODE ###

N = int(input())

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

m = 1

A.sort()
if A[0] == 0:
    print(0)
    exit(0)


for a in A:
    m = m * a

    if m > 1000000000000000000:
        print(-1)
        exit(0)



print(m)
### BUGGY CODE ###

f = int(input())
ls = [int(x) for x in input().split()]
a = c = max1 =0
for k in range(0, len(ls)-1):
    for a in range(k, f-1):
        if ls[a] < ls[a + 1]:
            break
        c = c + 1
    if c > max1:
        max1 = c
    c = 0
print(max1)

### FIXED CODE ###

f = int(input())
ls = [int(x) for x in input().split()]
a = c = max1 = k =0
while k < len(ls)-1:
    for a in range(k, len(ls)-1):
        if ls[a] < ls[a + 1]:
            break
        c = c + 1
    if c > max1:
        max1 = c
    k = a + 1
    c = 0
print(max1)
### BUGGY CODE ###

def main():
  n,m,s=map(int,input().split())
  uvab=[list(map(int,input().split())) for _ in range(m)]
  cd=[list(map(int,input().split())) for _ in range(n)]
  g=[[]for _ in range(n)]
  for u,v,a,b in uvab:
    g[u-1].append([v-1,a,b])
    g[v-1].append([u-1,a,b])
  import heapq
  from collections import defaultdict
  import math
  dp=[[math.inf]*(100*51)for _ in range(n)]
  kakutei=[[0]*(100*51)for _ in range(n)]
  dp[0][min(s,100*51-1)]=0
  todo=[[0,0,min(s,100*51-1)]] # [dp[v][i],v,i]
  heapq.heapify(todo)
  while sum([max(kakutei[i]) for i in range(n)])<n:
    _,v,i=heapq.heappop(todo)
    if kakutei[v][i]==1:
      continue
    kakutei[v][i]=1
    c,d=cd[v]
    # 両替
    dp[v][min(100*51-1,i+c)]=min(dp[v][min(100*51-1,i+c)],dp[v][i]+d)
    heapq.heappush(todo,[dp[v][min(100*51-1,i+c)],v,min(100*51-1,i+c)])
    # 鉄道
    l=g[v]
    for u,a,b in l:
      if i-a>=0 and kakutei[u][i-a]==0:
        dp[u][i-a]=min(dp[u][i-a],dp[v][i]+b)
        heapq.heappush(todo,[dp[u][i-a],u,i-a])
  for i in range(1,n):
    print(min(dp[i]))
  #for i in range(n):
  #  print(dp[i][:10])
if __name__=='__main__':
  #import datetime
  #print(datetime.datetime.now())
  main()
  #print(datetime.datetime.now())


### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
  n,m,s=map(int,input().split())
  uvab=[list(map(int,input().split())) for _ in range(m)]
  cd=[list(map(int,input().split())) for _ in range(n)]
  g=[[]for _ in range(n)]
  for u,v,a,b in uvab:
    g[u-1].append((v-1,a,b))
    g[v-1].append((u-1,a,b))
  import heapq
  inf=pow(10,21)
  max_s=50*50
  dp=[[inf]*(max_s+1)for _ in range(n)]
  kakutei=[[0]*(max_s+1)for _ in range(n)]
  dp[0][min(s,max_s)]=0
  todo=[[0,0,min(s,max_s)]] # [dp[v][i],v,i]
  heapq.heapify(todo)
  flgs=[0]*n
  flg=0
  ans=[inf]*n
  while flg<n:
    _,v,i=heapq.heappop(todo)
    if kakutei[v][i]==1:
      continue
    kakutei[v][i]=1
    if flgs[v]==0:
      flg+=1
      flgs[v]=1
    c,d=cd[v]
    ans[v]=min(ans[v],_)
    # 両替
    j=min(max_s,i+c)
    if kakutei[v][j]==0:
      dp[v][j]=min(dp[v][j],dp[v][i]+d)
      heapq.heappush(todo,[dp[v][j],v,j])
    # 鉄道
    l=g[v]
    for u,a,b in l:
      if i-a>=0 and kakutei[u][i-a]==0:
        dp[u][i-a]=min(dp[u][i-a],dp[v][i]+b)
        heapq.heappush(todo,[dp[u][i-a],u,i-a])
  print(*ans[1:],sep='\n')
if __name__=='__main__':
  main()
### BUGGY CODE ###

from math import ceil, log
from itertools import product


def solve(string):
    n = int(string)
    if n == 0:
        return "0"

    length = ceil(log(3 * n + 1, 4) -
                  1) * 2 if n > 0 else ceil(log(3 * abs(n) / 2 + 1, 4) - 1) * 2 + 1
    powers = [(-2)**i for i in range(length, -1, -1)]
    for digits in product("10", repeat=len(powers)):
        tmp = sum([_p if _d == "1" else 0 for _d, _p in zip(digits, powers)])
        if tmp == n:
            return "".join(digits)


if __name__ == '__main__':
    print(solve(input()))


### FIXED CODE ###

from math import ceil, log
from itertools import product


def solve(string):
    n = int(string)
    base = [2**i for i in range(1, 40)]
    inc = [(-2)**i for i in range(40)]
    ans = ""
    for b, i in zip(base, inc):
        if n % b >= b // 2:
            n -= i
            ans += "1"
        else:
            ans += "0"
        if n == 0:
            break
    return ans[::-1]


if __name__ == '__main__':
    print(solve(input()))
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    a = list(map(int,input().split()))
    ans = []
    for i in range(1,N+1):
        ans.append(a.index(i)+1)
    print(*ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    ans = [0]*N
    a = list(map(int,input().split()))
    for i in range(N):
        ans[a[i]-1] = i+1
    print(*ans)

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

s = list(input())
q = int(input())

for i in range(q):
    t = [x for x in input().split(" ")]
    if t[0] =='1':
        s = s[::-1]
    elif t[0] == '2':
        if t[1]== '1':
            s = list(t[2]) + s
        elif t[1] == '2':
            s = s + list(t[2])

print(''.join(s))


### FIXED CODE ###

from collections import deque

s = input()
d = deque()
header = 1
for i in s:
    d.append(i)
q = int(input())

for i in range(q):
    data = input().split()
    if len(data) == 1:
        header *= -1
    else:
        f = int(data[1])
        c = data[2]
        if header == 1:
            if f == 1:
                d.appendleft(c)
            else:
                d.append(c)
        else:
            if f == 1:
                d.append(c)
            else:
                d.appendleft(c)

if header == -1:
    d.reverse()

s = list(d)
s = "".join(s)

print(s)
### BUGGY CODE ###

import copy

X = int(input())


def cal(x, c):
    if x == 0:
        print(1)
        exit()

    else:
        now = x - 100
        for i in range(6):
            if now < i:
                return 0
            else:
                if c[i] > 19:
                    continue
                else:
                    cal(now-i, c[0:i:]+[c[i]+1]+c[i+1::])
    return 0


if X >= 2000:
    print(1)
else:
    print(cal(X, [0 for _ in range(7)]))


### FIXED CODE ###

X = int(input())
for c in range(X//100 + 1):
    if 100*c <= X and X <= 105*c:
        print(1)
        exit()

print(0)
### BUGGY CODE ###

n = int(input())
number = [int(x)+1 for x in range(n)]
#numberを一つずらしたリストを作成
I = number[1:]
I.append(number[0])

ans = 0
M = 0
for i in range(n):
    M = number[i]%I[i]
    ans += M
print(ans)

### FIXED CODE ###

n = int(input())

if n % 2 == 0:
    print(int((n+1)*(n//2)-n))
else:
    print(int(n*(n//2)))
### BUGGY CODE ###

import sys
N,K=list(map(int,sys.stdin.readline().split()))
H=list(map(int,sys.stdin.readline().split()))

dp=[0]*N

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

### FIXED CODE ###

import sys
N,K=list(map(int,sys.stdin.readline().split()))
H=list(map(int,sys.stdin.readline().split()))

dp=[0]*N

for i in range(1,N):
    mn=10**9
    for j in range(max(0,i-K),i):
        mn=min(mn,dp[j]+abs(H[j]-H[i]))

    dp[i]=mn

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

n = int(input())
s = list(map(int,input().split()))
ans = [s.index(i)+1 for i in range(1,n+1)]
print(*ans)

### FIXED CODE ###

# ABC 142 C go to school
n = int(input())
s = list(map(int,input().split()))

# ソートされたリストのインデックスを返す
s = sorted(range(len(s)), key=lambda k:s[k])
ans = [x+1 for x in s]
print(*ans)
### BUGGY CODE ###

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    return divisors

n = int(input())
ans = 0
for i in range(1, n):
    ans += len(make_divisors(i))
print(ans)

### FIXED CODE ###

n = int(input())
ans = 0
for i in range(1, n):
    ans += (n-1)//i
print(ans)
### BUGGY CODE ###

R,C,K=map(int,input().split())
item={}
for i in range(K):
    r,c,v=map(int,input().split())
    item[r-1,c-1]=0
    item[r-1,c-1]=v

dp=[[[0 for k in range(3)] for j in range(C)] for i in range(R)]

if (R-1,C-1) in item:
    dp[R-1][C-1][0]=item[R-1,C-1]
    dp[R-1][C-1][1]=item[R-1,C-1]
    dp[R-1][C-1][2]=item[R-1,C-1]

for j in range(C-2,-1,-1):
    if (R-1,j) in item:
        dp[R-1][j][0]=max(dp[R-1][j+1][1]+item[R-1,j],dp[R-1][j+1][0])
        dp[R-1][j][1]=max(dp[R-1][j+1][2]+item[R-1,j],dp[R-1][j+1][1])
        dp[R-1][j][2]=max(item[R-1,j],dp[R-1][j+1][2])
    else:
        dp[R-1][j][0]=dp[R-1][j+1][0]
        dp[R-1][j][1]=dp[R-1][j+1][1]
        dp[R-1][j][2]=dp[R-1][j+1][2]

for i in range(R-2,-1,-1):
    if (i,C-1) in item:
        dp[i][C-1][0]=dp[i+1][C-1][0]+item[i,C-1]
        dp[i][C-1][1]=dp[i+1][C-1][0]+item[i,C-1]
        dp[i][C-1][2]=dp[i+1][C-1][0]+item[i,C-1]
    else:
        dp[i][C-1][0]=dp[i+1][C-1][0]
        dp[i][C-1][1]=dp[i+1][C-1][0]
        dp[i][C-1][2]=dp[i+1][C-1][0]

for i in range(R-2,-1,-1):
    for j in range(C-2,-1,-1):
        if (i,j) in item:
            dp[i][j][0]=max(max(dp[i+1][j][0],dp[i][j+1][1])+item[i,j],dp[i][j+1][0])
            dp[i][j][1]=max(max(dp[i+1][j][0],dp[i][j+1][2])+item[i,j],dp[i][j+1][1])
            dp[i][j][2]=max(dp[i+1][j][0]+item[i,j],dp[i][j+1][2])
        else:
            dp[i][j][0]=max(dp[i+1][j][0],dp[i][j+1][0])
            dp[i][j][1]=max(dp[i+1][j][0],dp[i][j+1][1])
            dp[i][j][2]=max(dp[i+1][j][0],dp[i][j+1][2])

print(dp[0][0][0])


### FIXED CODE ###

import sys

input=sys.stdin.readline

R,C,K=map(int,input().split())
item=[[0 for i in range(C)] for j in range(R)]
for i in range(K):
    r,c,v=map(int,input().split())
    item[r-1][c-1]=v

dp=[[0 for i in range(3)] for j in range(C)]
dp[C-1][0]=item[R-1][C-1]
dp[C-1][1]=item[R-1][C-1]
dp[C-1][2]=item[R-1][C-1]

for j in range(C-2,-1,-1):
    dp[j][0]=max(dp[j+1][1]+item[R-1][j],dp[j+1][0])
    dp[j][1]=max(dp[j+1][2]+item[R-1][j],dp[j+1][1])
    dp[j][2]=max(item[R-1][j],dp[j+1][2])


for i in range(R-2,-1,-1):
    ndp=[[0 for i in range(3)] for j in range(C)]
    ndp[C-1][0]=dp[C-1][0]+item[i][C-1]
    ndp[C-1][1]=dp[C-1][0]+item[i][C-1]
    ndp[C-1][2]=dp[C-1][0]+item[i][C-1]
    for j in range(C-2,-1,-1):
        ndp[j][0]=max(max(dp[j][0],ndp[j+1][1])+item[i][j],ndp[j+1][0])
        ndp[j][1]=max(max(dp[j][0],ndp[j+1][2])+item[i][j],ndp[j+1][1])
        ndp[j][2]=max(dp[j][0]+item[i][j],ndp[j+1][2])
    dp=ndp

print(dp[0][0])
### BUGGY CODE ###

N, M = map(int, input().split())
H = list(map(int, input().split()))
grid = []
for i in range(M):
    array = list(map(int, input().strip().split()))
    grid.append(array)

flag = 0
X = 0

for a in range(1, N+1): #
    for b in grid:
        if b[0] == a:
            if H[b[1]-1] >= H[a-1]:
                flag = 1
        elif b[1] == a:
            if H[b[0]-1] >= H[a-1]:
                flag = 1

    if flag == 0:
        X += 1

    flag = 0

print(X)

### FIXED CODE ###

N, M = map(int, input().split())
H = list(map(int, input().split()))
grid = []
for i in range(M):
    array = list(map(int, input().strip().split()))
    grid.append(array)

flag = 0
X = 0

S = [1] * N


# for a in range(1, N+1):
#     for b in grid:
#         if b[0] == a:
#             if H[b[1]-1] >= H[a-1]:
#                 break
#         elif b[1] == a:
#             if H[b[0]-1] >= H[a-1]:
#                 break
#     else:
#         X += 1

for b in grid:
    if H[b[0]-1] > H[b[1]-1]:
        S[b[1]-1] = 0
    elif H[b[0]-1] < H[b[1]-1]:
        S[b[0]-1] = 0
    elif H[b[0]-1] == H[b[1]-1]:
        S[b[0] - 1] = 0
        S[b[1] - 1] = 0

X = sum(S)

print(X)
### BUGGY CODE ###

from functools import lru_cache

def main():
    N = int(input())
    infos = []
    for i in range(1,N):
        infos.append(tuple(map(int, input().split())))

    for i in range(1,N):
        current_time = 0
        for station_number in range(i,N):
            current_time = next_arrival_time(current_time, infos[station_number -1])
        print(current_time)
    print(0)

@lru_cache(maxsize = 10**6)
def next_arrival_time(current_time, info):
    if current_time <= info[1]:
        return info[1] + info[0]

    next_time = info[1]
    while next_time < current_time:
        next_time += info[2]

    return next_time + info[0]

main()

### FIXED CODE ###

from functools import lru_cache

def main():
    N = int(input())
    infos = []
    for i in range(1,N):
        infos.append(tuple(map(int, input().split())))

    for i in range(1,N):
        current_time = 0
        for station_number in range(i,N):
            current_time = next_arrival_time(current_time, infos[station_number -1])
        print(current_time)
    print(0)

@lru_cache(maxsize = 2**26)
def next_arrival_time(current_time, info):
    if current_time <= info[1]:
        return info[1] + info[0]

    next_time = current_time
    remainder = next_time % info[2]
    while remainder != 0:
        next_time += 1
        remainder = next_time % info[2]
    while next_time < current_time:
        next_time += info[2]

    return next_time + info[0]

main()
### BUGGY CODE ###

N, K = map(int, input().split())
H_list = list(map(int, input().split()))
if N-K <= 0:
    print(0)
else:
    for _ in range(K):
        A = H_list.index(max(H_list))
        H_list[A] = 0
    print(sum(H_list))

### FIXED CODE ###

N, K = map(int, input().split())
H_list = list(map(int, input().split()))
if N-K <= 0:
    print(0)
else:
    H_list.sort()
    print(sum(H_list[0:N-K]))
### BUGGY CODE ###

MOD = 10**9+7
list_size = (10**6+10)*4

f_list = [1]*list_size
f_r_list = [1]*list_size

for i in range(list_size - 1):
    f_list[i+1] = ((f_list[i] * (i+2)) % MOD)

f_r_list[-1] = pow(f_list[-1], MOD - 2, MOD)

for i in range(-2, -list_size-1, -1):
    f_r_list[i] = ((f_r_list[i+1] * (list_size + 2 + i)) % MOD)



r1,c1,r2,c2 = map(int,input().split())

ans = f_list[(r2+c2)*2]*f_r_list[r2*2]*f_r_list[c2*2]
ans %= MOD
ans += f_list[(r1+c1)*2]*f_r_list[r1*2]*f_r_list[c1*2]
ans %= MOD
ans -= f_list[(r2+c1)*2]*f_r_list[r2*2]*f_r_list[c1*2]
ans %= MOD
ans -= f_list[(c2+r1)*2]*f_r_list[c2*2]*f_r_list[r1*2]
ans %= MOD

print(ans)




### FIXED CODE ###

MOD = 10**9+7
r1,c1,r2,c2 = map(int,input().split())

size = 1010000*2
f_list = [1]*(size)
for i in range(1,size):
    f_list[i] = (f_list[i-1]*i)%MOD

def func(r,c):
    return (f_list[r+c]*pow(f_list[r],MOD-2,MOD)*pow(f_list[c],MOD-2,MOD))

ans = func(r2+1,c2+1)-1
ans += func(r1,c1)-1
ans -= func(r2+1,c1)-1
ans -= func(r1,c2+1)-1
print(ans%MOD)
### BUGGY CODE ###

N = int(input())
s= [input() for i in range(N)]
s=list(map(sorted,s))
ans=0
dp = list(range(N))

for i in range(N):
        for k in range(i+1,N):
                if dp[i] == dp[k]:
                        ans += 1
                else:
                        if s[i] == s[k]:
                                ans += 1
                                dp[k]=min(dp[i],dp[k])
                                dp[i]=dp[k]

print(ans)

### FIXED CODE ###

import math
def cmb(n, r):
        if r > n: 
                return 0
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


import collections
N = int(input())
s= [input() for i in range(N)]
ans=0
#各文字列文字列をソート
s=list(map(sorted,s))

s.sort()        #リストをソート
s=list(map(''.join,s))  #リストになっていたものを文字列に変換
clist = collections.Counter(s) #リスト内の各要素の数を数え上げ
kaisu=list(clist.values())

for i in kaisu:
        ans += cmb(i,2)

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

from collections import defaultdict
from collections import deque
import sys
sys.setrecursionlimit(10**6)

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

graph = defaultdict(deque)

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

arr = [0] * (n + 1)

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


def dfs(curr, root):
    stack = graph[curr]

    while stack:
        leaf = stack.pop()
        if leaf == root:
            continue
        arr[leaf] += arr[curr]
        dfs(leaf, curr)


dfs(1, -1)

print(*arr[1:])

### FIXED CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)

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

graph = defaultdict(set)

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

arr = [0] * (n + 1)

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


def solve():
    stack = [1]
    visited = [True] * 2 + [False] * (n - 1)

    while stack:
        curr = stack.pop()
        for leaf in graph[curr]:
            if visited[leaf]:
                continue
            stack.append(leaf)
            visited[leaf] = True
            arr[leaf] += arr[curr]

    return arr


arr = solve()

print(*arr[1:])
### BUGGY CODE ###

import logging

logger = logging.getLogger(__name__)
logger.setLevel(logging.DEBUG)
h = logging.FileHandler("logtest.log")
logger.addHandler(h)


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

logger.info("open_list: {}\n".format(open_list))

# 探索済みリスト
closed_list = [False] * N
closed_list[0] = True
cnt = 0
level = 1

# 深さ優先探索
def dfs(target):
    global cnt, level
    logger.info("***********open_list[target]: {}".format(open_list[target]))
    if all(closed_list):
        cnt += 1
        logger.info("[level: {}] closed_list: {}".format(level, closed_list))
        logger.info("cnt: {}".format(cnt))
        logger.info("*****************************************")
        return
    # open_listリストのnode
    for node in open_list[target]:
        logger.info("node: {}".format(node))
        logger.info("[level: {}] closed_list: {}".format(level, closed_list))
        # 探索済みでない場合
        if closed_list[node] is False:
            # 探索開始
            closed_list[node] = True
            # 再帰
            level += 1
            dfs(node)
            level = 1
            # levalを戻す
            closed_list[node] = False
            logger.info("[level: {}] closed_list: {}".format(level, closed_list))
    return


dfs(0)
print(cnt)


### FIXED CODE ###

# from log import logger

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

# logger.info('key_value: {}\n'.format(key_value))

closed_list = [False] * N
closed_list[0] = True
cnt = 0


def dfs(target):
    global cnt
    # logger.info('key_value[target]: {}'.format(key_value[target]))
    if all(closed_list):
        cnt += 1
        return
    for node in key_value[target]:
        # logger.info('node: {}'.format(node))
        # 探索済みでない場合
        if closed_list[node] is False:
            closed_list[node] = True
            dfs(node)
            closed_list[node] = False
        # logger.info('closed_list: {}\n'.format(closed_list))
    return


dfs(0)
print(cnt)