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

h, w = list(map(int, input().split()))
s = []
s.append("".join(["#" for i in range(w + 2)]))
for i in range(h):
    s.append("#" + input().strip() + "#")
s.append("".join(["#" for i in range(w + 2)]))

reps = []
for i in range(h + 2):
    for j in range(w + 2):
        if s[i][j] == ".":
            reps.append([i, j])
depths = []
for k in range(len(reps)):
    for l in range(k, len(reps), 1):
        start = reps[k]
        goal = reps[l]
        visits = [[-1 for i in range(w + 2)] for j in range(h + 2)]
        visits[goal[0]][goal[1]] = 1
        queue = [reps[k]]
        depth = 0

        while True:
            clear = False
            tmp_queue = []
            for now in queue:
                if visits[now[0]][now[1]] == 1:
                    clear = True
                    break
                else:
                    visits[now[0]][now[1]] = 0
                if (s[now[0] + 1][now[1]] == ".") and (visits[now[0] + 1][now[1]] != 0):
                    tmp_queue.append([(now[0] + 1), now[1]])
                if (s[now[0]][now[1] + 1] == ".") and (visits[now[0]][now[1] + 1] != 0):
                    tmp_queue.append([now[0], (now[1] + 1)])
                if (s[now[0] - 1][now[1]] == ".") and (visits[now[0] - 1][now[1]] != 0):
                    tmp_queue.append([(now[0] - 1), now[1]])
                if (s[now[0]][now[1] - 1] == ".") and (visits[now[0]][now[1] - 1] != 0):
                    tmp_queue.append([now[0], (now[1] - 1)])
            if clear:
                break
            else:
                depth += 1
                queue = tmp_queue
        depths.append(depth)
print(max(depths))


### FIXED CODE ###

from queue import Queue

h, w = list(map(int, input().split()))
s = []
for i in range(h):
    s.append(input().strip())

ans = 0
for i in range(h):
    for j in range(w):
        start = s[i][j]
        if start == "#":
            continue
        else:
            visited = [[False for _ in range(w)] for _ in range(h)]
            visited[i][j] = True
            queue = Queue()
            queue.put((i, j, 0))

            while 0 < queue.qsize():
                now = queue.get()
                ans = max(ans, now[2])

                if (now[0] <= (h - 2)) and (s[now[0] + 1][now[1]] == ".") and not visited[now[0] + 1][now[1]]:
                    queue.put(((now[0] + 1), now[1], (now[2] + 1)))
                    visited[now[0] + 1][now[1]] = True
                if (now[1] <= (w - 2)) and (s[now[0]][now[1] + 1] == ".") and not visited[now[0]][now[1] + 1]:
                    queue.put((now[0], (now[1] + 1), (now[2] + 1)))
                    visited[now[0]][now[1] + 1] = True
                if (1 <= now[0]) and (s[now[0] - 1][now[1]] == ".") and not visited[now[0] - 1][now[1]]:
                    queue.put(((now[0] - 1), now[1], (now[2] + 1)))
                    visited[now[0] - 1][now[1]] = True
                if (1 <= now[1]) and (s[now[0]][now[1] - 1] == ".") and not visited[now[0]][now[1] - 1]:
                    queue.put((now[0], (now[1] - 1), (now[2] + 1)))
                    visited[now[0]][now[1] - 1] = True

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

N = int(input())
S = input()
ans = set()
c0done = set()
for i0 in range(N - 2):
    c0 = S[i0]
    if c0 in c0done:
        continue
    c0done.add(c0)
    for i1 in range(i0 + 1, N - 1):
        c1 = S[i1]
        for c2 in set(S[i1+1:]):
            ans.add(c0 + c1 + c2)
print(len(ans))

### FIXED CODE ###

N = int(input())
S = tuple(map(int, input()))

ans = 0
pins = [0] * 3
for pin in range(1000):
    pins[0] = pin // 100
    pins[1] = (pin % 100) // 10
    pins[2] = pin % 10
    x = 0
    for c in S:
        if c == pins[x]:
            x += 1
            if x == 3:
                ans += 1
                break
print(ans)
### BUGGY CODE ###

NM = input().split(" ")
A_LIST = input().split(" ")
A = []
for i in A_LIST:
    A.append(int(i))

N = int(NM[0])
M = int(NM[1])

A.sort()
for i in range(0, M):
    m = max(A)
    m = m // 2
    A[N-1] = m
    if m >= max(A):
        pass
    else:
        A.sort()
S = 0
for i in A:
    S += i
print(S)

### FIXED CODE ###

import heapq

NM =input().split(" ")
A_LIST = input().split(" ")
N = int(NM[0])
M = int(NM[1])

A = []
for i in A_LIST:
    heapq.heappush(A, -1 * int(i))
    
for i in range(0, M):
    m = heapq.heappop(A)
    m = -1 * m
    m = m // 2
    heapq.heappush(A, -1 * m)

S = 0    
for i in A:
    S += (-1 * i)

print(S)
### BUGGY CODE ###

N = int(input())

dct = {}

for i in range(N):
    s = input()
    if not s in dct:
        dct[s] = 1

    else:
        dct[s] +=  1
    
ans = []
for key in dct.keys():
    if dct[key] == max(dct.values()):
        ans.append(key)

for j in sorted(ans):
    print(j)

### FIXED CODE ###

N = int(input())

dct = {}

for i in range(N):
    s = input()
    if not s in dct:
        dct[s] = 1

    else:
        dct[s] +=  1
    
m = max(dct.values())
for s in sorted(k for k in dct if dct[k] == m):
    print(s)
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
c = [float("INF")] * n
c[0] = 0
for i in range(1, min(n, k + 1)):
    c[i] = abs(h[i] - h[0])

for i in range(2, n):
    for j in range(1, k + 1):
        c[i] = min(c[i], c[i - j] + abs(h[i] - h[i - j]))

print(c[n - 1])


### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
c = [float("INF")] * n
c[0] = 0
for i in range(1, n):
    for j in range(1, min(n, k + 1)):
        c[i] = min(c[i], c[i - j] + abs(h[i] - h[i - j]))

print(c[n - 1])
### BUGGY CODE ###

n=int(input())
a=[]
b=[]
c=[]
d=0

for i in range(1,n):
    if n%i==0:
        a.append(int(n//i))
        b.append(i)
        d += 1

for i in range(d):
    c.append(a[i]+b[i])


print(min(c)-2)

### FIXED CODE ###

n=int(input())
a=[]

for i in range(1,int(n//(n**0.5))+1):
    if n%i==0:
        a.append(int(n//i)+i)
        
print(min(a)-2)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
for i in range(N):
    print(str(A.index(i+1)+1), end=' ')

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A_dict = dict(zip(A,range(1, N+1)))

for i in range(N):
  print(A_dict[i+1], end=' ')
### BUGGY CODE ###

S=input()

ans=0
while "ABC" in S:
  ind=S.index("ABC")
  S=list(S)
  S[ind]="B"
  S[ind+1]="C"
  S[ind+2]="A"
  S="".join(S)
  ans+=1
print(ans)

### FIXED CODE ###

S=list(input())

nS=[]
i=0
while i<len(S)-1:
  if S[i]=="B" and S[i+1]=="C":
    nS.append("D")
    i+=1
  else:
    nS.append(S[i])
  i+=1
    
t=[]
nl=[]
for i in nS:
  if i=="A" or i=="D":
    nl.append(i)
  else:
    if nl:
      t.append(nl)
      nl=[]
if nl:
  t.append(nl)


ans=0
for i in t:
  dn=0
  for j in range(len(i)):
    if i[j]=="D":
      ans+=j-dn
      dn+=1

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

def segfunc(x, y):
    return min(x, y)

class segment_():
    def __init__(self, init_val, n, segfunc):
        self.ide_ele = 10**9+1
        # num: n以上の最小の2のべき乗
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele]*2*self.num
        self.segfunc = segfunc
        # set_val
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]
        # built
        for i in range(self.num-2, -1, -1):
            self.seg[i] = self.segfunc(self.seg[2*i+1], self.seg[2*i+2])

    def update(self, k, x):
        k += self.num - 1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[2*k+1], self.seg[2*k+2])

    def query(self, p, q):
        if q <= p:
            return self.ide_ele
        p += self.num - 1
        q += self.num - 2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

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

    seg_ = segment_(A, n, lambda a, b: min(a, b))
    ans = 10**19
    for k in range(n):
        t = k*x
        for i in range(n):
            if k <= i:
                t += seg_.query(i-k, i+1)
            else:
                t += min(seg_.query(0, i+1), seg_.query(n-(k-i), n))
        ans = min(t, ans)
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

n, x = map(int,sys.stdin.readline().split())
A = list(map(int,sys.stdin.readline().split()))

ans = 10**18
mins = [a for a in A]
for k in range(n):
    for i in range(n):
        if k <= i:
            mins[i] = min(A[i-k], mins[i])
        else:
            mins[i] = min(A[n-(k-i)], mins[i])
    ans = min(sum(mins)+k*x, ans)
print(ans)
### BUGGY CODE ###

from fractions import gcd

N,M=map(int,input().split())
#List=list(map(lambda x:int(x)/2,input().split()))
List=list(map(int,input().split()))


LCM=1
cut2count=0
a=List[0]/2
while a%2==0:
    a/=2
    cut2count+=1

for i in List:
    i/=2
    LCM*=i/gcd(LCM,i)
        
    cut2countb=0
    b=i
    while b%2==0:
        b/=2
        cut2countb+=1
    if cut2count!=cut2countb:
        print(0)
        exit()


#for i in List:
 #   if LCM/i%2==0:
  #      print(0)
   #     exit()

print(int(M//(LCM*2)+M%(LCM*2)//LCM))


### FIXED CODE ###

from fractions import gcd
import sys
input = sys.stdin.readline

N,M=map(int,input().split())
List=list(map(lambda x:int(x)//2,map(int, set(input().split()))))

def main():
    LCM=1

    for i in List:
        LCM*=i//gcd(LCM,i)

    for i in List:
        if LCM//i%2==0:
            print(0)
            exit()

    print(int(M//(LCM*2)+M%(LCM*2)//LCM))


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

e = list(map(int,input().split()))
a = e[0]
b = e[1]
c = e[2]
d = e[3]
cnt = 0
t = [j for j in range(a,b+1) if j%c != 0 and j%d != 0]

for i in t:
    if (int(i/c)-i/c != 0) and (int(i/d)-i/d != 0):
        cnt += 1
    else:
        pass
print(cnt)

### FIXED CODE ###

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

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

def sums(x):
    S1 = x//c
    S2 = x//d
    S3 = x// (c*d//gcd(c,d))
    return x - S1 - S2 + S3


print(sums(b)-sums(a-1))
### BUGGY CODE ###

def main():
    import sys
    input=sys.stdin.readline

    h,w,k=map(int,input().split())
    sy,sx,gy,gx=map(int,input().split())

    maze=[]
    for _ in range(h):
        maze.append(tuple(input()))

    #maze=[list(input()) for _ in range(h)]

    sy-=1
    sx-=1
    gy-=1
    gx-=1

    #maze[sy][sx]="S"

    dis=[[-1]*w for _ in range(h)]

    from collections import deque

    dis[sy][sx]=0



    d = deque([(sx,sy)])
    while len(d)>0:
        (x,y)=d.popleft()
        if x==gx and y==gy:
            print(dis[gy][gx])
            #maze[gy][gx]="G"

            #pri(dis)
            #pri(maze)

            exit()

        for (mx,my) in ((0,1),(1,0),(-1,0),(0,-1)):
            #print(mx,my,d)
            for j in range(1,k+1):
                nx=x+mx*j
                ny=y+my*j
                #print(y,x,">>",ny,nx)
                if 0<=nx<w and 0<=ny<h:
                    if maze[ny][nx]=="." and (dis[ny][nx]==-1 or dis[ny][nx]==dis[y][x]+1):
                        dis[ny][nx]=dis[y][x]+1
                        d.append((nx,ny))
                        #pri(dis)
                    else:
                        break
                else:
                    break

    print(-1)
        
if __name__ == '__main__':
    main()


                










### FIXED CODE ###

def main():
    import sys
    from collections import deque
    input=sys.stdin.readline

    h,w,k=map(int,input().split())
    sy,sx,gy,gx=map(int,input().split())

    #maze=[]
    #for _ in range(h):
    #    maze.append(tuple(input()))

    maze=[tuple(input()) for _ in range(h)]

    sy-=1
    sx-=1
    gy-=1
    gx-=1

    #maze[sy][sx]="S"

    dis=[[-1]*w for _ in range(h)]



    dis[sy][sx]=0



    d = deque([(sx,sy)])
    while len(d)>0:
        (x,y)=d.popleft()
        if x==gx and y==gy:
            print(dis[gy][gx])
            #maze[gy][gx]="G"

            #pri(dis)
            #pri(maze)

            exit()

        for (mx,my) in ((0,1),(1,0),(-1,0),(0,-1)):
            #print(mx,my,d)
            for j in range(1,k+1):
                nx=x+mx*j
                ny=y+my*j
                #print(y,x,">>",ny,nx)
                if 0<=nx<w and 0<=ny<h:
                    if maze[ny][nx]=="." and (dis[ny][nx]==-1 or dis[ny][nx]==dis[y][x]+1):
                        if dis[ny][nx]==-1:
                            d.append((nx,ny))
                        dis[ny][nx]=dis[y][x]+1
                        
                        #pri(dis)
                    else:
                        break
                else:
                    break

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

s = input()
a = int(s)
mods = [a%2019]
for i in range(len(s)):
  a = a-int(s[i])*10**(len(s)-i-1)
  mods.append(a%2019)
mod_N = {}
for i in mods:
  mod_N[i] = 0
for i in mods:
  mod_N[i] += 1
ans = 0
for i in mod_N:
  ans += mod_N[i]*(mod_N[i]-1)/2
print(int(ans))

### FIXED CODE ###

s = input()
a = 0
mods = [0]*2019
mods[a] += 1
r = 1
for i in s[::-1]:
  a = (a+int(i)*r)%2019
  r = r*10%2019
  mods[a] += 1
ans = 0
for i in mods:
  ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
al = list(map(int, input().split()))

visited= [1]
for i in range(K):
    next_town  = al[visited[i] - 1]
    if next_town in visited:
        loop_sta = visited.index((next_town)) #　visited_townsにおけるループ開始のインデックス
        loop_end = len(visited) #visited_townsにおけるループの終わりのインデックス
        loop_length = loop_end - loop_sta #繰り返すループの長さ
        amari = (K - loop_sta) % loop_length
        ans = visited[loop_sta + amari]
        print(ans)
        exit()
    else:
        visited.append(next_town)
else:
    print(visited[-1])



### FIXED CODE ###

from collections import defaultdict


def inpl():
    return list(map(int, input().split()))


N, K = inpl()
aa = inpl()

s = 1

route = [s]
ed = set([s])

for i in range(1, K + 1):
    s = aa[s - 1]
    if s in ed:
        Li = route.index(s)
        Ri = len(route)
        idx = Li + (K - Li) % (Ri - Li)
        print(route[idx])
        break
    else:
        route.append(s)
        ed.add(s)
        continue
else:
    print(s)
### BUGGY CODE ###

import re

s = input()
re_list = [r'dream$', r'dreamer$', r'erase$', r'eraser$']
while True:
  if s == '':
    print('YES')
    break
  for regex in re_list:
    m = re.sub(regex, '', s)
    if m != s:
      s = m
      break
  else:
    print('NO')
    break
  continue

### FIXED CODE ###

S = input()
S = S[::-1]
while len(S) != 0:
  num = len(S)
  if S.find('maerd') == 0:
    S = S.replace('maerd', '', 1)
  if S.find('remaerd') == 0:
    S = S.replace('remaerd', '', 1)
  if S.find('esare') == 0:
    S = S.replace('esare', '', 1)
  if S.find('resare') == 0:
    S = S.replace('resare', '', 1)
  if num == len(S):
    print('NO')
    exit(0)
print('YES')
### BUGGY CODE ###

import math
A,B,N=map(int,input().split())
range_list=range(N+1)
max_value=0
for i in range(N+1):
    check_value=math.floor(A*i/B)-A*math.floor(i/B)
    if(max_value<=check_value):
        max_value=check_value
print(max_value)


### FIXED CODE ###

A,B,N=map(int,input().split())
if B<=N:
    print(int(A*(B-1)/B)-A*int((B-1)/B))
else:
    print(int(A*(N)/B)-A*int(N/B))
### BUGGY CODE ###

s=input()
l=len(s)
mod = pow(10,9)+7

dp = [[0 for i in range(13)] for j in range(l+1)]
dp[0][0] = 1
#dp[i][j]=i桁目までを13で割った時、
#そのあまりがjになる場合の数

for i in range(1,l+1):
	num = s[-i]
	keta = pow(10,i-1)
	if num == '?':
		for j in range(10):
			for k in range(13):
				dp[i][(j * keta + k) % 13] += dp[i-1][k]
	else:
		for k in range(13):
			dp[i][(int(num) * keta + k) % 13] += dp[i-1][k]
print(dp[l][5] % mod)

### FIXED CODE ###

INF = 10 ** 9 + 7

S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i + 1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= INF
    else:
        k = int(x)
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= INF
    mul = mul * 10 % 13  # 計算量削減のためここで13で割っている

print(dp[len(S)][5])
### BUGGY CODE ###

k, s = list(map(int, input().split()))
ans = 0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if (x + y + z) == s:
                ans += 1
print(ans)


### FIXED CODE ###

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

from heapq import heapify,heappop,heappush
N,M=map(int,input().split())
S,T=map(int,input().split())
Graph=[set() for i in range(N)]
Edge=[]
mod=10**9+7
inf=float("inf")
for i in range(N):
  Edge.append((i,i,0))
for i in range(M):
  a,b,c=map(int,input().split())
  Graph[a-1].add((c,b-1))
  Graph[b-1].add((c,a-1))
  Edge.append((a-1,b-1,c))
  Edge.append((b-1,a-1,c))
def dijkstra(s,n,links):
  Visited=[False]*n
  cost=[inf]*n
  P=[0]*n
  P[s]=1
  cost[s]=0
  heap=[(0,s)]
  heapify(heap)
  while heap:
    hc,hp=heappop(heap)
    for c,p in links[hp]:
      if Visited[p]:
        continue
      if c+hc<cost[p]:
        cost[p]=c+hc
        P[p]=P[hp]
        heappush(heap,(cost[p],p))
      elif c+hc==cost[p]:
        P[p]=(P[p]+P[hp])%mod
    Visited[hp]=True
  return cost,P
  
cost_S,P_S=dijkstra(S-1,N,Graph)
cost_T,P_T=dijkstra(T-1,N,Graph)
D=cost_S[T-1]
List=[]
for a,b,c in Edge:
  if cost_S[a]+c+cost_T[b]==D and cost_S[a]<D/2 and cost_T[b]<D/2 and c>0:
    List.append((P_S[a]*P_T[b])%mod)
  if cost_S[a]+c+cost_T[b]==D and cost_S[a]==D/2 and cost_T[b]==D/2 and c==0:
    List.append((P_S[a]*P_T[b])%mod)
Sum=0
for i in List:
  Sum=(Sum+i)%mod
ans=0
for i,c in enumerate(List):
  ans=(ans+(Sum-List[i])*List[i])%mod
print(ans)



      
  
  
  
  


### FIXED CODE ###

from heapq import heapify,heappop,heappush
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
S,T=map(int,input().split())
Graph=[set() for i in range(N)]
Edge=[]
mod=10**9+7
inf=float("inf")
for i in range(M):
  a,b,c=map(int,input().split())
  Graph[a-1].add((c,b-1))
  Graph[b-1].add((c,a-1))
  Edge.append((a-1,b-1,c))
  Edge.append((b-1,a-1,c))
def dijkstra(s,n,links):
  Visited=[False]*n
  cost=[inf]*n
  P=[0]*n
  P[s]=1
  cost[s]=0
  heap=[(0,s)]
  heapify(heap)
  while heap:
    hc,hp=heappop(heap)
    if Visited[hp]:
      continue
    Visited[hp]=True
    for c,p in links[hp]:
      if Visited[p]:
        continue
      if c+hc<cost[p]:
        cost[p]=c+hc
        P[p]=P[hp]
        heappush(heap,(cost[p],p))
      elif c+hc==cost[p]:
        P[p]=(P[p]+P[hp])%mod
  return cost,P

def dp(s,n,links,d):
  Visited=[False]*n
  cost=[inf]*n
  P=[0]*n
  P[s]=1
  cost[s]=0
  heap=[(0,s)]
  heapify(heap)
  while heap:
    hc,hp=heappop(heap)
    if 2*hc>d:
      break
    if Visited[hp]:
      continue
    Visited[hp]=True
    for c,p in links[hp]:
      if Visited[p]:
        continue
      if c+hc<cost[p]:
        cost[p]=c+hc
        P[p]=P[hp]
        heappush(heap,(cost[p],p))
      elif c+hc==cost[p]:
        P[p]=(P[p]+P[hp])%mod
  return cost,P

cost_S,P_S=dijkstra(S-1,N,Graph)
D=cost_S[T-1]
cost_T,P_T=dp(T-1,N,Graph,D)
Pat=P_S[T-1]
ans=(Pat**2)%mod
for a,b,c in Edge:
  if cost_S[a]+cost_T[b]+c==D:
    if 2*cost_S[a]<D and 2*cost_T[b]<D:
      ans-=((P_S[a]*P_T[b])**2)%mod
for i in range(N):
  if 2*cost_S[i]==2*cost_T[i]==D:
    ans-=((P_S[i]*P_T[i])**2)%mod
print(ans%mod)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(1000000)


n, q = [int(i) for i in input().split()]
ab = [[] for _ in range(n)]
for _ in range(n - 1):
    i, j = [int(i)-1 for i in input().split()]
    ab[i].append(j)
    ab[j].append(i)
p = [0]*n
for _ in range(q):
    i, j = [int(i) for i in input().split()]
    p[i-1] += j

al = [False]*n
pp = [0]*n


def a(i=0, j=0):
    al[i] = True
    j += p[i]
    pp[i] = str(j)
    for k in ab[i]:
        if not al[k]:
            a(k, j)


a()
print(" ".join(pp))


### FIXED CODE ###

import sys

sys.setrecursionlimit(1000000)


def input():
    return sys.stdin.readline()


n, q = [int(i) for i in input().split()]
ab = [[] for _ in range(n)]
for _ in range(n - 1):
    i, j = [int(i)-1 for i in input().split()]
    ab[i].append(j)
    ab[j].append(i)
p = [0]*n
for _ in range(q):
    i, j = [int(i) for i in input().split()]
    p[i-1] += j

al = [False]*n
pp = [0]*n


def a(i=0, j=0):
    al[i] = True
    j += p[i]
    pp[i] = str(j)
    for k in ab[i]:
        if not al[k]:
            a(k, j)


a()
print(" ".join(pp))
### BUGGY CODE ###

#! /usr/local/bin/python3
# coding: utf-8

from itertools import product
from math import inf
from sys import setrecursionlimit

setrecursionlimit(10000)

ws = []
min_weight = inf


def swap(w, i, j):
    tmp = w[i]
    w[i] = w[j]
    w[j] = tmp


def try_next(w, total, hand):
    global min_weight

    if total > min_weight:
        return

    if w == ws:
        min_weight = min(total, min_weight)
        return

    for i, j in product(range(len(w)), range(len(w))):
        if i >= j:
            continue
        wnew = w[:]
        swap(wnew, i, j)
        hnew = hand[:]
        hnew.append((i, j))
        try_next(wnew, total + w[i] + w[j], hnew)

    return


def first_try(w):
    global ws

    weight = 0
    for i in reversed(range(len(w))):
        j = w.index(ws[i])
        if i != j:
            weight += w[i] + w[j]
            swap(w, i, j)
    return weight


def main():
    global ws, min_weight

    n = int(input())
    w = [int(x) for x in input().split()]
    ws = sorted(w)

    min_weight = first_try(w[:])
    try_next(w, 0, [])
    print(min_weight)


main()



### FIXED CODE ###

def solve(n, A):
    def cycles():
        V = [False] * n
        B = sorted(A)
        T = {B[i]: i for i in range(n)}
        C = []

        for i in range(n):
            if V[i]:
                continue
            cur = i
            cycle = []
            while not V[cur]:
                V[cur] = True
                cycle.append(cur)
                cur = T[A[cur]]
            C.append(cycle)

        return C

    ans = 0
    s = min(A)

    for cycle in cycles():
        S = sum([A[i] for i in cycle])
        m = min([A[i] for i in cycle])
        an = len(cycle)
        ans += min(S + (an - 2) * m, m + S + (an + 1) * s)

    return ans


def main():
    n = int(input())
    A = [int(x) for x in input().split()]

    print(solve(n, A))


main()
### BUGGY CODE ###

n,x,m = map(int,input().split())
a = []
a.append(0)
a.append(x)
isBreak = False
for i in range(1,n):
  #tmp = (a[i]**2)%m
  tmp = (a[i]%m)*(a[i]%m)
  tmp = tmp%m
  if tmp==0:
    break
  if tmp in a:
    isBreak = True
    break
  a.append(tmp)
#print(a)
if isBreak:
  i = 1
  while a[i]!=tmp:
    i+=1
  kurikaeshi = len(a) - i
  goukei = sum(a[i:])
  #print(goukei)
  tmp=(n-(len(a)-1))
  #print(tmp//kurikaeshi)
  a.append(tmp//kurikaeshi * goukei)
  #print(a)
  tmp = tmp%kurikaeshi
  if tmp!=0:
    t = sum(a[i:i+tmp])
    a.append(t)
print(sum(a))

### FIXED CODE ###

n,x,m = map(int,input().split())
a = []
a.append(0)
a.append(x)
isBreak = False
for i in range(1,n):
  #tmp = (a[i]**2)%m
  tmp = (a[i]%m)*(a[i]%m)
  tmp = tmp%m
  if tmp==0:
    break
  if tmp in a:
    isBreak = True
    break
  a.append(tmp)
#print(a)
if isBreak:
  i = 1
  while a[i]!=tmp:
    i+=1
  kurikaeshi = len(a) - i
  goukei = sum(a[i:])
  #print(goukei)
  tmp=(n-(len(a)-1))
  #print(tmp//kurikaeshi)
  a.append(tmp//kurikaeshi * goukei)
  #print(a)
  tmp = tmp%kurikaeshi
  if tmp!=0:
    t = sum(a[i:i+tmp])
    a.append(t)
print(sum(a))