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

h,w = map(int, input().split())
mat = [[True] * (w+2)]
for _ in range(h):
    mat.append([True] + [a == '#' for a in input()] + [True])
mat.append([True]*(w+2))

prev = []
for i in range(1,h+1):
    for j in range(1,w+1):
        if mat[i][j]:
            prev.append((i,j))

round = -1
while prev:
    #print(prev)
    #print(mat)
    round += 1
    next = []
    for (x,y) in prev:
        if not mat[x-1][y]:
            next.append((x-1,y))
            mat[x-1][y] = True
        if not mat[x][y-1]:
            next.append((x,y-1))
            mat[x][y-1] = True
        if not mat[x+1][y]:
            next.append((x+1,y))
            mat[x+1][y] = True
        if not mat[x][y+1]:
            next.append((x,y+1))
            mat[x][y+1] = True
    prev = next

print(round)


### FIXED CODE ###

import functools as ft

h,w = map(int, input().split())
mat = [[True] * (w+2)]
for _ in range(h):
    mat.append([True] + [a == '#' for a in input()] + [True])
mat.append([True]*(w+2))

prev = []
for i in range(1,h+1):
    for j in range(1,w+1):
        if mat[i][j]:
            prev.append((i,j))



round = -1
while prev:
    round += 1
    #print(prev)
    #print(mat)
    def calc(next, tup):
        x = tup[0]
        y = tup[1]
        if not mat[x-1][y]:
            next.append((x-1,y))
            mat[x-1][y] = True
        if not mat[x][y-1]:
            next.append((x,y-1))
            mat[x][y-1] = True
        if not mat[x+1][y]:
            next.append((x+1,y))
            mat[x+1][y] = True
        if not mat[x][y+1]:
            next.append((x,y+1))
            mat[x][y+1] = True
        return next
    next = ft.reduce(calc, prev, [])

    prev = next

print(round)
### BUGGY CODE ###

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

H ,W = map(int, input().split())#↓H行数 →W列数
#List = [list(str(input())) for i in range(H)]
#H=3
#W=3
#List=[['.', '.', '.'], ['.', '#', '.'], ['.', '.', '.']]
cheak=[['0' for i in range(W)] for j in range(H)]

q = deque([])
List=[]
for h in range(H):
    qwe=list(str(input()))
    List.append(qwe)
    for w in range(W):
        if qwe[w]=='#':
            cheak[h][w]='1'
            q.append([h,w])
#print(List)
#print(cheak)
move=[[1,0],[-1,0],[0,1],[0,-1]]
num=-1
#print(q)
while q:
    for rt in range(len(q)):
        i=q.popleft()
        for u in move:
            if 0<=i[0]+u[0]<=H-1 and 0<=i[1]+u[1]<=W-1 and cheak[i[0]+u[0]][i[1]+u[1]]=='0':
                q.append([i[0]+u[0],i[1]+u[1]])
                cheak[i[0]+u[0]][i[1]+u[1]]='1'
    #print(cheak)
    num+=1
print(num)   

### FIXED CODE ###

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

H ,W = map(int, input().split())#↓H行数 →W列数
List = [list(str(input())) for i in range(H)]
#H=3
#W=3
#List=[['.', '.', '.'], ['.', '#', '.'], ['.', '.', '.']]
cheak=[['0' for i in range(W)] for j in range(H)]

q = deque([])

for h in range(H):
    for w in range(W):
        if List[h][w]=='#':
            cheak[h][w]='1'
            q.append([h,w])
#print(List)
#print(cheak)
move=[[1,0],[-1,0],[0,1],[0,-1]]
num=-1
#print(q)
while q:
    for rt in range(len(q)):
        i=q.popleft()
        for u in move:
            if 0<=i[0]+u[0]<=H-1 and 0<=i[1]+u[1]<=W-1 and cheak[i[0]+u[0]][i[1]+u[1]]=='0':
                q.append([i[0]+u[0],i[1]+u[1]])
                cheak[i[0]+u[0]][i[1]+u[1]]='1'
    #print(cheak)
    num+=1
print(num)
### BUGGY CODE ###

n = int(input())
listn = list(map(int,input().split()))

ans = 0
for i in range(1,n+1):
    if min(listn[:i]) >= listn[i-1]:
        ans += 1

print(ans)
    



### FIXED CODE ###

n = int(input())
listn = list(map(int,input().split()))

a = 10**6
ans = 0
for i in range(n):
    if listn[i] <= a:
        a = listn[i]
        ans += 1

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

import sys
input = sys.stdin.readline

def main():
    N, M, P = map(int, input().split())
    abc = [list(map(int, input().split())) for i in range(M)]
    INF = int(1e10)
    cost = [INF] * (N + 1)

    cost[1] = 0
    count = 0
    fin = False
    while True:
        no_change = True
        for i in range(M):
            a, b, c = abc[i]
            tmp = cost[a] - (c - P)
            if cost[b] > tmp:
                cost[b] = tmp
                no_change = False
        count += 1
        if no_change:
            fin = True
            break
        
        if count == N:
            pre = cost[N]
        elif count > 2 * N:
            break
        elif count > N:
            if pre != cost[N]:
                break
    
    if fin:
        print(max(0, -cost[N]))
    else:
        if pre != cost[N]:
            print(-1)
        else:
            print(max(0, -cost[N]))

if __name__ == "__main__":
    main()

### FIXED CODE ###

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

def belman(egdes, N, start, end):
    INF = int(1e10)
    cost = [INF] * N
    cost[start] = 0
    fin = False
    count = 0
    while True:
        no_change = True
        for edge in egdes:
            from_, to_, d = edge
            tmp = cost[from_] + d
            if cost[to_] > tmp:
                no_change = False
                cost[to_] = tmp
        count += 1
        if no_change:
            fin = True
            break
        elif count > N+1:
            break
    
    if fin:
        return max(0, -cost[end])
    else:
        return -1

def bfs(link, N, start):
    q = deque()
    check = [False] * N
    q.append(start)
    check[start] = True
    used = {start}
    while len(q) > 0:
        node = q.popleft()
        for next_ in link[node]:
            if not check[next_]:
                check[next_] = True
                q.append(next_)
                used.add(next_)
    return used
        

def main():
    N, M, P = map(int, input().split())

    link = [[] for i in range(N)]
    rlink = [[] for i in range(N)]
    edges = []

    for i in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        link[a].append(b)
        rlink[b].append(a)
        edges.append((a, b, -(c-P)))
    
    use_nodes = bfs(link, N, 0) & bfs(rlink, N, N-1)
    use_edges = [(a, b, c) for a, b, c in edges if a in use_nodes and b in use_nodes]
    print(belman(use_edges, N, 0, N-1))

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

from fractions import gcd
from functools import reduce

MOD = 10 ** 9 + 7
N = int(input())
A = list(map(int, input().split()))

L = reduce(lambda x, y: x * y // gcd(x, y), set(A))

ans = 0
for i in range(N):
    ans += L // A[i]
    ans %= MOD
print(ans)


### FIXED CODE ###

from fractions import gcd
from functools import reduce

MOD = 10 ** 9 + 7
N = int(input())
A = list(map(int, input().split()))

L = reduce(lambda x, y: x * y // gcd(x, y), A)

ans = 0
for i in range(N):
    ans += L // A[i]
print(ans % MOD)
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)
  
k = int(input())
s = 0
l = []
for i in range(k):
  for j in range(k):
    l.append(gcd(i+1,j+1))
for h in range(k):
  for n in l:
    s += gcd(h+1, n)
print(s)


### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)
  
k = int(input())
s = 0
l = []
for i in range(k):
  for j in range(k):
    l.append(math.gcd(i+1,j+1))
for h in range(k):
  for n in l:
    s += math.gcd(h+1, n)
print(s)
### BUGGY CODE ###

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

mod = 1000000007

def pow(x, n):
    ret = 1
    while n > 0:
        if (n & 1) == 1:
            ret = (ret * x) % mod
        x = (x * x) % mod
        n //= 2
    return ret

def inv(n):
    return pow(n, mod - 2)

def fac(n):
    ret = 1
    for i in range(1, n + 1):
        ret = (ret * i) % mod
    return ret

def cmb(n, k):
    if k < 0 or k > n:
        return 0
    return (fac(n) * inv(fac(k)) * inv(fac(n - k))) % mod

x = max(0, n - k - 1)
ret = cmb(n * 2 - 1, n - 1)
for i in range(x):
    ret = (ret - cmb(n, i + 1) * cmb(n - 1, i)) % mod
print(ret)



### FIXED CODE ###

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

mod = 1000000007

def pow(x, n):
    ret = 1
    while n > 0:
        if (n & 1) == 1:
            ret = (ret * x) % mod
        x = (x * x) % mod
        n //= 2
    return ret

fac = [1]
inv = [1]
for i in range(n * 2):
    fac.append(fac[-1] * (i + 1) % mod)
    inv.append(pow(fac[-1], mod - 2))

def cmb(n, k):
    if k < 0 or k > n:
        return 0
    return (fac[n] * inv[k] * inv[n - k]) % mod

x = max(0, n - k - 1)
ret = cmb(n * 2 - 1, n - 1)
for i in range(x):
    ret = (ret - cmb(n, i + 1) * cmb(n - 1, i)) % mod
print(ret)
### BUGGY CODE ###

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

for i in range(n):
    A.append(int(input()))

B = [1]
i = 0
while(len(B) == len(set(B))):
    t = A[B[-1] - 1]
    i += 1
    if t == 2:
        break
    B.append(t)
if t == 2:
    print(i)
else:
    print(-1)

### FIXED CODE ###

n = int(input())
N = []
for i in range(n):
    N.append(int(input()))

t = 0
for i in range(n+2):
    if N[t] == 2:
        break
    else:
        t = N[t] - 1
if i == n+1:
    print(-1)
else:
    print(i+1)
### BUGGY CODE ###

n = int(input())
attends = [int(each) for each in input().split(' ')]
ordered = sorted(attends)
for each in ordered:
    print(attends.index(each) + 1, end=' ')


### FIXED CODE ###

from operator import itemgetter
n = int(input())
ordered_info = [ [i, int(num)] for i, num in zip(range(n), input().split(' '))]
ordered_info.sort(key = itemgetter(1))
ans = ''
for i, _ in ordered_info:
    print(i+1, end=' ')
### BUGGY CODE ###

n = int(input())
An = list(map(int, input().split()))

An.sort()

idx = 0

while True:
    if idx == len(An):
        ans = len(An) - An.count(0)
        print(ans)
        exit()

    flg = False
    if An[idx] != 0:
        for i in range(idx + 1, len(An)):
            if An[i] != 0 and An[i] % An[idx] == 0:
                if An[i] == An[idx]:
                    flg = True
                An[i] = 0
        if flg:
            An[idx] = 0

    idx += 1

### FIXED CODE ###

n = int(input())
An = list(map(int, input().split()))

An.sort()
max_num = An[-1]

primes = [True] * max_num
once = [False] * max_num

i = 0
while i < n:
    once[An[i] - 1] = True

    j = 1
    while i + j < n:
        if An[i] == An[i + j]:
            once[An[i] - 1] = False
            j += 1
        else:
            break

    i += j

for i in range(n):
    if primes[An[i] - 1]:
        base = An[i]
        idx = An[i] * 2 - 1
        while idx < max_num:
            primes[idx] = False
            idx += base

ans = [x and y for (x, y) in zip(once, primes)]
print(ans.count(True))
### BUGGY CODE ###

import re

pattern = re.compile(r'01|10')

def remove(tower, count):
  target = len(pattern.findall(tower))
  if target:
    remove(pattern.sub('', tower), count + target)
  else:
    print(count * 2)

count = 0
remove(input(), count)

### FIXED CODE ###

s = input()
zero = len([x for x in s if x == "0"])
one = len(s) - zero

print(min(zero, one) * 2)
### BUGGY CODE ###

import numpy as np

h, w = map(int, input().split())
S = [str(input()) for _ in range(h)]
data = []
for s in S:
  row = []
  for c in s:
    row.append(1 if c=='.' else 0)
  data.append(row)
data = np.array(data, dtype=int)

def get_dp(d, width):
  dp = d.copy()
  for i, row in enumerate(d):
    for j in range(1, width):
      val = row[j]
      if val > 0:
        n = dp[i][j-1]
        dp[i][j] += n
        for k in range(n):
          dp[i][j-k-1] += 1
  return dp

dp_row = get_dp(data, w)
dp_col = get_dp(data.T, h)
print((dp_row+dp_col.T).max() - 1)

### FIXED CODE ###

import numpy as np

h, w = map(int, input().split())
S = list(list(input()) for _ in range(h))
S = np.array(S)
S_int = np.zeros_like(S, dtype=int)
S_int[S=='.'] = 1

def getLR(d, width, height):
  L = np.zeros_like(d)
  R = L.copy()
  L[:][0] = 0
  R[:][-1] = 0
  for i in range(1, width):
    ridx = width - 1 - i
    L[:,i] = d[:,i] * (L[:,i-1] + d[:,i-1])
    R[:,ridx] = d[:,ridx] * (R[:,ridx+1] + d[:,ridx+1])
  return L, R

L, R = getLR(S_int, w, h)
U, D = getLR(S_int.T, h, w)
print((L+R+U.T+D.T).max() + 1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Mon Jun  1 16:47:45 2020

@author: NEC-PCuser
"""

N = int(input())
S = input()
count = 0
for i in range(0, 1000):
    j = 0
    a = str(i).zfill(3)
    for k in range(0, N):
        if (a[j] == S[k]):
            j += 1
        if (j == 3):
            count += 1
            break
            
print(count)

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Mon Jun  1 16:47:45 2020

@author: NEC-PCuser
"""

N = int(input())
S = input()
count = 0
for i in range(0, 1000):
    j = 0
    a = str(i).zfill(3)
    b = S.find(a[0])
    if b == -1:
        continue
    c = S[b+1:].find(a[1])
    if c == -1:
        continue
    d= S[b+c+2:].find(a[2])
    if d != -1:
        count += 1
    
            
print(count)
### BUGGY CODE ###

def line(s):
    ret = [0] * len(s)
    for i in range(len(s)):
        ret[i] = 0 if s[i] == 'W' else 1

    return ret

def all_same(arr):
    for i in range(len(arr)-1):
        if arr[i] != arr[i+1]:
            return False
    return True

def opposite(x):
    return (x - 1) ** 2

def update(arr):
    count = 0
    while(not all_same(arr)):
        append = opposite(arr[-1])
        other = arr[-1]
        i = -1
        while(arr[i] == other or -i == len(arr) + 1):
            arr[i] = append
            i -= 1
        if -i == len(arr)/2:
            arr.reverse()
        count += 1
    return count

if __name__ == '__main__':
    s = raw_input()
    arr = line(s)
    print(update(arr))


### FIXED CODE ###

def line(s):
    ret = [0] * len(s)
    for i in range(len(s)):
        ret[i] = 0 if s[i] == 'W' else 1

    return ret

def count(arr):
    c = 0
    for i in range(len(arr)-1):
        if arr[i+1] != arr[i]:
            c += 1
    return c

if __name__ == '__main__':
    s = raw_input()
    arr = line(s)
    print(count(arr))
### BUGGY CODE ###

n = int(input())
a = []
A = input()
B = input()
C = input()
a = sorted([int(i) for i in A.split()])
b = sorted([int(i) for i in B.split()])
c = sorted([int(i) for i in C.split()])

ans = 0
for i in b:
    a_small = len([x for x in a if x < i])
    c_large = len([x for x in c if x > i])
    ans += a_small * c_large
print(ans)


### FIXED CODE ###

import math
from math import modf

n = int(input())
A = input()
B = input()
C = input()
a = [(int(i) + 0.1) for i in A.split()]
b = [int(i) for i in B.split()]
c = [(int(i) - 0.1) for i in C.split()]
al = sorted(a + b + c)
ans = 0
a_count = 0
c_count = n
for i in al:
    decimal, integer = modf(i)
    if decimal > 0.8:
        c_count -= 1
    elif decimal > 0.05:
        a_count += 1
    else:
        ans += a_count * c_count
print(ans)
### BUGGY CODE ###

N, K = map( int, input().split() )
x = list( map( int, input().split() ))
 
ret = 10 ** 18
for i in range( N - K + 1 ):
  s = x[ i: K + i ]
  l, r = s[ 0 ], s[ K - 1 ]
  ret = min( ret, abs( l - r ) + min( abs( r ), abs( l ) ) )
print( ret )

### FIXED CODE ###

N, K = map( int, input().split() )
x = list( map( int, input().split() ))
 
ret = 10 ** 18
for i in range( N - K + 1 ):
  l, r = x[i], x[ K + i - 1 ]
  ret = min( ret, abs( l - r ) + min( abs( r ), abs( l ) ) )
print( ret )
### BUGGY CODE ###

from functools import lru_cache

MOD = pow(10, 9) + 7

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

@lru_cache(maxsize=H*W)
def calc(h, w):
    if h == H -1 and w == W -1:
        return 1
    count = 0
    # right
    if w + 1 < W  and A[h][w + 1] == ".":
        count += calc(h, w + 1)
        count %= MOD

    if h + 1 < H  and A[h + 1][w] == ".":
        count += calc(h + 1, w)
        count %= MOD

    return count % MOD

for w in reversed(range(W)):
    for h in reversed(range(H)):
        calc(h, w)
print(calc(0,0))


### FIXED CODE ###

from functools import lru_cache

MOD = pow(10, 9) + 7

H, W = map(int, input().split())
A = [input() for _ in range(H)]
dp = [ [0 for j in range(W + 1)] for i in range(H + 1)]

for w in range(1, W + 1):
    for h in range(1, H + 1):
        if w == 1 and h == 1:
            dp[1][1] = 1
            continue
 
        if A[h-1][w-1] == '.':
            dp[h][w] = (dp[h-1][w] + dp[h][w-1]) % MOD
            continue
        if A[h-1][w-1] == '#':
            dp[h][w]  = 0



print(dp[H][W])
### BUGGY CODE ###

def main():
    N, K = map(int, input().split())
    XY = [tuple(map(int, input().split())) for _ in range(N)]
    XY.sort()
    XY = tuple(XY)

    def count(x_min, x_max, y_min, y_max, i, j):
        OK = 0
        # NG = 0
        a = j - i + 1 - K
        for m in XY[i:j + 1]:
            if y_min <= m[1] <= y_max:
                OK += 1
        if OK >= K:
            return True
        return False

    ans = 10 ** 20
    for i, val_i in enumerate(XY[:N - 1]):
        a = val_i[0]
        for j, val_j in enumerate(XY[i + K - 1:N]):
            b = val_j[0]
            e = b - a
            # print (e, i, j)
            for k in XY:
                c = k[1]
                for l in XY:
                    d = l[1]
                    if c < d:
                        if count(a, b, c, d, i, j + i + K - 1):
                            # print ('A')
                            ans = min(ans, e * (d - c))
    print (ans)
    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

#PythonだとTLEする
N, K = map(int, input().split())
X = [0] * N
Y = [0] * N
for i in range(N):
    x, y = map(int, input().split())
    X[i] = x
    Y[i] = y

def count(x_min, x_max, y_min, y_max):
    cnt = 0
    for i in range(N):
        if x_min <= X[i] <= x_max and y_min <= Y[i] <= y_max:
            cnt += 1
    return cnt

ans = 10 ** 20
for i in range(N):
    for j in range(N):
        for k in range(N):
            for l in range(N):
                # print ('i, j , k, l = ', i, j, k, l)
                if X[i] < X[j] and Y[k] < Y[l]:
                    if count(X[i], X[j], Y[k], Y[l]) >= K:
                        # print ('A')
                        ans = min(ans, (X[j] - X[i]) * (Y[l] - Y[k]))
print (ans)
### BUGGY CODE ###

range = xrange
input = raw_input
MOD = 10**9+7

def main():
    n = int(input())

    dp = [0] * (1 << n)
    for i in [i >> 1 for i, x in enumerate(input()) if x == '1']:
        dp[1 << i] = 1

    npow = 1 << n

    for i in range(n - 1):
        _dp = [0] * npow
        for j in [i >> 1 for i, x in enumerate(input()) if x == '1']:
            jpow = 1 << j
            for mask,val in enumerate(dp):
                if not mask & jpow:
                    _dp[mask + jpow] += val
        for mask in range(npow):
            _dp[mask] %= MOD
        dp = _dp

    print(sum(dp) % MOD)

main()

### FIXED CODE ###

range = xrange
input = raw_input
MOD = 10**9+7
 
n = int(input())

dp = [0] * (1 << n)
for i in [i for i, x in enumerate(input().split()) if x == '1']:
    dp[1 << i] = 1

npow = 1 << n

for i in range(n - 1):
    _dp = [0] * npow
    for j in [i for i, x in enumerate(input().split()) if x == '1']:
        jpow = 1 << j
        mask = 0
        while mask < npow:
            _dp[mask + jpow] += dp[mask]
            mask += 1 + ((mask+1) & jpow)
    for mask in range(npow):
        _dp[mask] %= MOD
    dp = _dp
 
print(sum(dp) % MOD)
### BUGGY CODE ###

#-*-coding:utf-8-*-

def main():
    N = int(input())
    x_list = list(map(int, input().split()))
    med_dict = {}

    med = (N // 2) -1

    for i in x_list:
        if i in med_dict:
            print(med_dict[i])
        else:
            removed_x_list = x_list[:]
            removed_x_list.remove(i)
            removed_x_list.sort()
            median = removed_x_list[med]
            med_dict[i] = median
            print(median)
    #print(med_dict)

    
if __name__ == '__main__':
    main()

### FIXED CODE ###

#-*-coding:utf-8-*-

def main():
    N = int(input())
    x_list = list(map(int, input().split()))
    x_list_sort = x_list[:]
    x_list_sort.sort()
    med1 = x_list_sort[(N//2)-1]
    med2 = x_list_sort[N//2]
    for i in x_list:
        if i <= med1:
            print(med2)
        elif i >= med2:
            print(med1)
            
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N, K = (int(x) for x in input().split())
Plot = [tuple(int(x) for x in input().split()) for _ in range(N)]
X = [p[0] for p in Plot]
Y = [p[1] for p in Plot]
X.sort()
Y.sort()
#全2点間で長方形の辺を作り、その内内部点がK個のものだけ面積を比較する。
ans = 10e20
from itertools import combinations
for x1, x2 in combinations(X, 2):
    for y1, y2 in combinations(Y, 2):
        S = (x2-x1)*(y2-y1)
        cnt = sum(x1 <= p[0] <= x2 and y1 <= p[1] <= y2 for p in Plot)
        if cnt == K and S != 0:
            ans = min(ans, S)
print(ans)


### FIXED CODE ###

N, K = (int(x) for x in input().split())
Plot = [tuple(int(x) for x in input().split()) for _ in range(N)]
X = [p[0] for p in Plot]
Y = [p[1] for p in Plot]
X.sort()
Y.sort()
#全2点間で長方形の辺を作り、その内内部点がK個のものだけ面積を比較する。
ans = 10e20
from itertools import combinations
for x1, x2 in combinations(X, 2):
    for y1 in Y:
        y2 = [y for x,y in Plot if x1 <= x <= x2 and y1 <= y]
        if len(y2) < K:
            break
        y2.sort()
        S = (x2-x1)*(y2[K-1]-y1)
        ans = min(ans, S)
print(ans)
### BUGGY CODE ###

# https://atcoder.jp/contests/abc138/tasks/abc138_d

from collections import deque

def bfs(graph, start, query):
    queue = deque([])
    acc = query[start] if start in query else 0
    queue.append([start, acc])
    ans = {start:acc}

    while queue:
        idx, acc = queue.popleft()
        for child in graph[idx].keys():
            if child in ans:
                continue
            ans[child] = acc
            if child in query:
                ans[child] += query[child]
            queue.append([child, ans[child]])
    [print(ans[i], end=' ') for i in range(1, n+1)]

n,q = map(int, input().split())
tree = {}
start = 1
for i in range(n-1):
    a,b = map(int, input().split())
    if a not in tree:
        tree[a] = {}
    tree[a][b] = 1
    if b not in tree:
        tree[b] = {}
    tree[b][a] = 1

query = {}
for _ in range(q):
    p, x = map(int,input().split())
    if p not in query:
        query[p] = x
    else:
        query[p] += x
bfs(tree, start, query)


### FIXED CODE ###

# https://atcoder.jp/contests/abc138/tasks/abc138_d

from collections import deque

def bfs(graph, start, query, n):
    queue = deque([])
    acc = query[start] if start in query else 0
    queue.append([start, acc])
    ans = [-1] * n
    ans[start] = acc

    while queue:
        idx, acc = queue.popleft()
        for child in graph[idx].keys():
            if ans[child] >= 0:
                continue
            ans[child] = acc
            if child in query:
                ans[child] += query[child]
            queue.append([child, ans[child]])
    
    print(' '.join(map(str, ans)))

n,q = map(int, input().split())
tree = {}
start = 0
for i in range(n-1):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    if a not in tree:
        tree[a] = {}
    tree[a][b] = 1
    if b not in tree:
        tree[b] = {}
    tree[b][a] = 1

query = {}
for _ in range(q):
    p, x = map(int,input().split())
    p -= 1
    if p not in query:
        query[p] = x
    else:
        query[p] += x
bfs(tree, start, query, n)
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

K = int(input())

sum_ans = 0
for i in range(1, K+1):
    for j in range(1, K+1):
        for k in range(1, K+1):
            sum_ans += gcd(i, j, k)

print(sum_ans)

### FIXED CODE ###

import math

K = int(input())

sum_ans = 0
gcd_list = []
for i in range(1, K+1):
    for j in range(1, K+1):
        tmp = math.gcd(i, j)
        gcd_list.append(tmp)

for k in range(1, K+1):
    for g in gcd_list:
            tmp = math.gcd(k, g)
            sum_ans += tmp

print(sum_ans)