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

n, q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n - 1)]
px = [list(map(int, input().split())) for _ in range(q)]

x_sorted = [0] * n
for i in range(q):
    p = px[i][0]
    x = px[i][1]
    x_sorted[p - 1] += x

# print(x_sorted)

cost = dict() # コストテーブル
for i, j in ab:
    cost[i - 1] = cost.get(i - 1, []) + [(j - 1, x_sorted[i - 1])]

d = [0 for i in range(n)]
qq = [(d[0], 0)]
while qq:
    (du, u) = qq.pop()
    for v, weight in cost.get(u, []):
        alt = du + weight
        d[v] = alt
        qq.append((alt, v))

ans_list = []
for i in range(n):
    ans_list.append(str(d[i] + x_sorted[i]))

print(' '.join(ans_list))


### FIXED CODE ###

from sys import stdin
from collections import defaultdict

if __name__ == '__main__':
    n, q = map(int, stdin.readline().rstrip().split())
    ab = [list(map(int, stdin.readline().rstrip().split())) for _ in range(n - 1)]
    px = [list(map(int, stdin.readline().rstrip().split())) for _ in range(q)]

    g = defaultdict(list)
    for a, b in ab:
        a -= 1
        b -= 1
        g[a].append(b)
        g[b].append(a)

    adder = defaultdict(int)
    for p, x in px:
        p -= 1
        adder[p] += x

    ans = [float('inf')] * n
    ans[0] = adder[0]
    qu = [0]

    while qu:
        cur = qu.pop()

        for target in g[cur]:
            if ans[target] == float('inf'):
                ans[target] = ans[cur] + adder[target]
                qu.append(target)

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

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

for i in range(N - 1):
  head = H[i]
  remains = min(H[i + 1:])
  if head - remains >= 2:
    print("No")
    break
else:
  print("Yes")

### FIXED CODE ###

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

head = 0

for i in range(N):
  if H[i] >= head:
    head = H[i]
  if head - H[i] >= 2:
    print("No")
    break
else:print("Yes")
### BUGGY CODE ###

N = int(input())
a_list = list(map(int, input().split()))
result_list = [0] * N

for i in range(N):
    for a in a_list:
        if i == a:
            result_list[i-1] += 1

# 最後の改行を削除
result_list_str = [str(i) for i in result_list]
print('\n'.join(result_list_str))


### FIXED CODE ###

N = int(input())
a_list = list(map(int, input().split()))
result_list = [0] * N

for a in a_list:
    result_list[a-1] += 1

result_list_str = [str(i) for i in result_list]
print('\n'.join(result_list_str))
### BUGGY CODE ###

k,q=map(int,input().split())
D=list(map(int,input().split()))
for i in range(q):
    n,x,m=map(int,input().split())
    mD=list(map(lambda i: i%m, D)) #元の列のmodを取る
    a=(n-1)//k
    b=(n-1)%k
    ans=0
    ans+=mD.count(0)*a+mD[:b].count(0) #0の数
    cnt=x%m+sum(mD)*a+sum(mD[:b]) #増えた量
    ans+=cnt//m
    print(n-1-ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

k,q=map(int,input().split())
D=list(map(int,input().split()))
A=[]
for i in range(q):
    n,x,m=map(int,input().split())
    mD=list(map(lambda i: i%m, D)) #元の列のmodを取る
    ans=0
    cnt=x%m
    a=(n-1)//k
    b=(n-1)%k
    for d in mD[:b]: #mod kで余る部分
        if d==0:
            ans+=a+1
        cnt+=d*(a+1)
    for d in mD[b:]: #余らない部分
        if d==0:
            ans+=a
        cnt+=d*a
    ans+=cnt//m
    print(n-1-ans)
### BUGGY CODE ###

def main():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    _max = max
    _min = min
    for _ in range(k):
        C = [0] * n
        for i in range(n):
            a = A[i]
            l = _max(0, i - a)
            r = _min(n, i + a + 1)
            C[l] += 1
            if r < n:
                C[r] -= 1
        r = 0
        for i in range(n):
            r += C[i]
            A[i] = r
        if A == [n] * n:
            break
    print(" ".join(map(str, A)))
main()


### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    _max = max
    _min = min
    for _ in range(k):
        C = [0] * n
        i = 0
        for a in A:
            l = _max(0, i - a)
            r = _min(n, i + a + 1)
            C[l] += 1
            if r < n:
                C[r] -= 1
            i += 1
        r = 0
        for i in range(n):
            r += C[i]
            A[i] = r
        if A == [n] * n:
            break
    print(" ".join(map(str, A)))
main()
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
ans = 1
for a in A:
  ans *= a
print(ans if ans <= 10**18 else -1)

### FIXED CODE ###

def main():
  n = int(input())
  A = list(map(int, input().split()))
  ans = 1
  if 0 in A:
    print(0)
    return
  for a in A:
    ans *= a
    if ans > 10**18:
      print(-1)
      return
  print(ans)

main()
### BUGGY CODE ###

def main():
    N = int(input())
    A = [int(_) for _ in input().split()]



    result = 1
    for i in A:
        result = result * i

    if result > 1000000000000000000:
        print(-1)
    else:
        print(result)

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N = int(input())
    A = [int(_) for _ in input().split()]

    if 0 in A:
        print(0)
        return

    result = 1
    # count = 0
    for i in A:
        # l = len(str(i)) - 1
        # if l != 0:
        #     count = count + l
        result = result * i
        if result > 1000000000000000000:
            print(-1)
            return

    print(result)

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

import itertools


def main():
    n = int(input())
    s = input()
    index = [i for i in range(n)]
    comb = itertools.combinations(index, 3)
    ans = 0
    for c in comb:
        if c[1] - c[0] == c[2] - c[1]:
            continue
        if s[c[0]] != s[c[1]] and s[c[0]] != s[c[2]] and s[c[1]] != s[c[2]]:
            ans += 1
    return ans


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


### FIXED CODE ###

def main():
    n = int(input())
    s = input()
    # Positions for each character.
    r = set()
    g = set()
    r_add = r.add
    g_add = g.add
    for ind, c in enumerate(s):
        if c == 'R':
            r_add(ind)
        elif c == 'G':
            g_add(ind)
    b = set(range(n)) - r - g

    ans = 0
    for i in r:
        for j in g:
            p, q = min(i, j), max(i, j)
            if (q - p) % 2 == 0 and (p + q) // 2 in b:
                ans -= 1
            if (q + (q - p)) in b:
                ans -= 1
            if (p - (q - p)) in b:
                ans -= 1
            ans += len(b)
    return ans


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

n,m,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
ans=0
i=0
while i<=n:
    if sum(a[:i])>k:
        break
    else:
        time=sum(a[:i])
        if time+sum(b)<=k:
            max_b=m
        else:
            for j in range(m):
                if time+b[j]<=k:
                    time+=b[j]
                else:
                    max_b=j
                    break
        ans_i=max_b+i
        ans=max(ans_i,ans)
        i+=1
print(ans)

### FIXED CODE ###

n,m,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
x,y=[0],[0]
for i in range(n):
    x.append(a[i]+x[i])
for j in range(m):
    y.append(b[j]+y[j])

ans=0
j=m
for i in range(n+1):
    if x[i]>k:
        break
    while y[j]>k-x[i]:
        j-=1
    ans=max(i+j,ans)
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
L = sorted(list(map(int, input().split())))

ans = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        ans += sum(L[i] + L[j] > l for l in L[j+1:])

print(ans)


### FIXED CODE ###

import sys
import bisect
input = sys.stdin.readline

N = int(input())
L = sorted(list(map(int, input().split())))
ans = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        index = bisect.bisect_left(L, L[i] + L[j])
        n = index - j - 1
        ans += n

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

n = int(input())
a = list(map(int,input().split()))
g = []
ans = 0
for j in range(60):
    d = 0
    for i in range(n):
        if a[i]&1:
            d += 1
        a[i] >>= 1
    g.append(d)
for i in range(60):
    ans += g[i]*(n-g[i])*(pow(2,i,10**9+7))
print(ans%(10**9+7))

### FIXED CODE ###

import numpy as np

n = int(input())
arr = np.array([int(i) for i in input().split()])
mod = 10 ** 9 + 7
s = 0

for i in range(60):
    c1 = np.count_nonzero(arr & 1) # 自分がnp.sumを利用したがどうしても正解になれなかった。なぜ？
    s += 2 ** i * c1 * (n - c1)
    arr >>= 1

print(s % mod)
### BUGGY CODE ###

from operator import mul
from functools import reduce

n = int(input())
a = list(map(int, input().split()))
ans = reduce(mul, a)

if ans > 1e18:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
if 0 in A:
    print(0)
    exit()
ans = 1
for a in A:
    ans *= a
    if ans > 10 ** 18:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

import sys

import numpy as np
from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import dijkstra

sys.setrecursionlimit(10000)
INF = float('inf')

N, M, S, T = list(map(int, input().split()))
U = []
V = []
A = []
B = []
for _ in range(M):
    u, v, a, b = list(map(int, input().split()))
    U.append(u)
    V.append(v)
    A.append(a)
    B.append(b)

graph_yen = coo_matrix((A, (U, V)), shape=(N + 1, N + 1))
graph_snuke = coo_matrix((B, (U, V)), shape=(N + 1, N + 1))

# yen_mins[i]: S から i まで行くときの最小金額
yen_mins = dijkstra(graph_yen.tocsr(), indices=S, directed=False, unweighted=False)
# snuke_mins[i]: T から i まで行くときの最小金額
snuke_mins = dijkstra(graph_snuke.tocsr(), indices=T, directed=False, unweighted=False)

# total_mins[i]: i で両替して S から T まで行くときの最小金額
total_mins = 10 ** 15 - (yen_mins + snuke_mins)[1:]

# 後ろから累積最大値とる
for a in np.maximum.accumulate(total_mins[::-1])[::-1]:
    print(int(a))


### FIXED CODE ###

import heapq
import sys

import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')


def dijkstra(graph, start):
    """
    :param list of (list of (int, int)) graph:
    :param int start:
    :return:
    """
    dist = [INF for _ in range(len(graph))]
    dist[start] = 0
    heap = []
    heapq.heappush(heap, (0, start))

    while len(heap) > 0:
        w, v = heapq.heappop(heap)
        if w > dist[v]:
            continue
        for u, dw in graph[v]:
            if w + dw < dist[u]:
                dist[u] = w + dw
                heapq.heappush(heap, (w + dw, u))
    return dist


N, M, S, T = list(map(int, input().split()))
graph_yen = [[] for _ in range(N + 1)]
graph_snuuk = [[] for _ in range(N + 1)]
for _ in range(M):
    u, v, a, b = list(map(int, input().split()))
    graph_yen[u].append((v, a))
    graph_yen[v].append((u, a))
    graph_snuuk[u].append((v, b))
    graph_snuuk[v].append((u, b))

# yen_mins[i]: S から i まで行くときの最小金額
yen_mins = np.array(dijkstra(graph_yen, start=S))
# snuke_mins[i]: T から i まで行くときの最小金額
snuke_mins = np.array(dijkstra(graph_snuuk, start=T))

# totals[i]: i で両替して S から T まで行くときの最大金額
totals = 10 ** 15 - (yen_mins + snuke_mins)[1:]
# 後ろから累積最大値とる
for a in np.maximum.accumulate(totals[::-1])[::-1]:
    print(int(a))
### BUGGY CODE ###

MOD = 10 ** 9 + 7


def power_expo(x, y):
    """Returns x^y.

    <https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6>
    """
    if y == 0:
        return 1
    elif y == 1:
        return x % MOD
    elif y % 2 == 0:
        return power_expo(x, y // 2) ** 2 % MOD
    else:
        return power_expo(x, y // 2) ** 2 * x % MOD


def main():
    x, y = [int(x) for x in input().split()]
    if (x + y) % 3 != 0:
        return 0
    summ = (x + y) // 3     # d + r
    diff = x - y  # d - r
    if summ % 2 != diff % 2:
        return 0
    d = (summ + diff) // 2  # Down
    r = (summ - diff) // 2  # Right
    if d < 0 or r < 0:
        return 0
    chosen = min(d, r)

    patterns = 1

    for i, j in zip(range(summ - chosen + 1, summ + 1), range(1, summ + 1)):
        patterns = patterns * i % MOD * power_expo(j, MOD - 2) % MOD

    return patterns


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

# やはり難しい，再び解説。割り算のときは mod 10^9+7 が厄介。
# とりあえず，割る方は 10^9+5 乗して掛ければいいらしい。


### FIXED CODE ###

MOD = 10 ** 9 + 7


def power_expo(x, y):
    """Returns x^y.

    <https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6>

    結局, 組み込み関数の `pow()` のほうが速そう. 第3引数でmodもできる.
    """
    if y == 0:
        return 1
    elif y % 2 == 0:
        return power_expo(x, y // 2) ** 2 % MOD
    else:
        return power_expo(x, y // 2) ** 2 * x % MOD


def main():
    x, y = [int(x) for x in input().split()]
    if (x + y) % 3 != 0:
        return 0
    summ = (x + y) // 3     # d + r
    diff = x - y  # d - r
    if summ % 2 != diff % 2:
        return 0
    d = (summ + diff) // 2  # Down
    r = (summ - diff) // 2  # Right
    if d < 0 or r < 0:
        return 0
    chosen = min(d, r)

    patterns = 1

    for i, j in zip(range(summ - chosen + 1, summ + 1), range(1, summ + 1)):
        patterns = patterns % MOD * i % MOD * pow(j, MOD - 2, MOD) % MOD

    return patterns


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

# やはり難しい，再び解説。割り算のときは mod 10^9+7 が厄介。
# とりあえず，割る方は 10^9+5 乗して掛ければいいらしい。
### BUGGY CODE ###

def isPrime(p):
	if p == 2: return 1
	if p < 2 or p&1 == 0: return 0
	return 1 if pow(2,p-1,p) == 1 else 0

while True:
	try:
		n = int(raw_input())
		print sum(isPrime(i) for i in range(1,n+1))
	except:
		break

### FIXED CODE ###

import math
n = []
while True:
    try:
        n.append(int(raw_input()))
    except:
        break
  
r = max(n)+1
sqrt = int(math.sqrt(r))
p = [1]*r
p[0] = 0
p[3::2] = [0 for x in range(3,r,2)]
for i in range(2,sqrt,2):
    if p[i]:
        p[2*i+1::i+1] = [0 for x in range(2*i+1,r,i+1)] 
  
for i in n:
     print sum(p[:i])
### BUGGY CODE ###

import sys
def solve():
    readline = sys.stdin.readline

    N, M, K = map(int, readline().split())
    *A, = map(int, readline().split())

    def gen(S, k):
        s = t = 0
        it = iter(range(N)).__next__
        i = k-1
        for a, b in zip(S[k-2:], A[k-1:]):
            while s < t and Q1[t-1] <= a:
                t -= 1
            i = it()
            Q0[t] = i-1; Q1[t] = a
            t += 1

            yield Q1[s] + b*k

            if s < t and Q0[s] <= i-M:
                s += 1

    S = A[:]
    T = [0]*N
    Q0 = [0]*N; Q1 = [0]*N
    for k in range(2, K+1):
        S[k-1:] = gen(S, k)
    print(max(S))
solve()

### FIXED CODE ###

import sys
def solve():
    readline = sys.stdin.readline

    N, M, K = map(int, readline().split())
    *A, = map(int, readline().split())

    S = A[:]
    T = [0]*N
    Q0 = [0]*N; Q1 = [0]*N
    for k in range(2, K+1):
        s = t = 0

        for i in range(k-1, N):
            a = S[i-1]
            while s < t and Q1[t-1] <= a:
                t -= 1
            Q0[t] = i-1; Q1[t] = a
            t += 1

            T[i] = Q1[s] + A[i]*k

            if s < t and Q0[s] <= i-M:
                s += 1
        S, T = T, S
    print(max(S))
solve()
### BUGGY CODE ###

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

def bina(x,ok,ng):
    global da
    if ng-ok==1:
        return ok
    mi=(ng+ok)//2
    if da[mi]<x:
        ok=mi
    else:
        ng=mi
    return bina(x,ok,ng)

ans=0
da=sorted(da)
for i in range(1,n-1):
    for j in range(i):
        ans+=bina(da[i]+da[j],i,n)-i
print(ans)

### FIXED CODE ###

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

def bina(x,ok,ng):
    global da
    while ng-ok!=1:
        mi=(ok+ng)//2
        if da[mi]<x:
            ok=0
            ok+=mi
        else:
            ng=0
            ng+=mi
    return ok


ans=0
da=sorted(da)
for i in range(1,n-1):
    for j in range(i):
        ans+=bina(da[i]+da[j],i,n)-i
print(ans)
### BUGGY CODE ###

import queue
n,x,y = map(int,input().split())

adj = [[] for i in range(n)]

adj[x-1].append(y-1)
adj[y-1].append(x-1)

for i in range(n-1):
    adj[i].append(i+1) 
    adj[i+1].append(i)
        
ans = [0 for _ in range(n+1)]

def bfs(start):
    inf = 1001001001
    q = queue.Queue()
    q.put(start)
    dist = [inf]*n
    dist[start] = 0
    
    while not q.empty():
        v = q.get()

        for i in adj[v]:
            if dist[i] == inf:
                dist[i] = dist[v] + 1
                q.put(i)

    for i in range(n):
        ans[dist[i]] += 1

for i in range(n):
    bfs(i)

for i in range(1,n):
    print(ans[i]//2)

### FIXED CODE ###

n,x,y=map(int,input().split())

ans=[0]*n

for i in range(1,n):
    for j in range(i+1,n+1):
        d=min(abs(j-i),abs(x-i)+1+abs(j-y))
        ans[d]+=1


for i in range(1,n):
    print(ans[i])
### BUGGY CODE ###

X,Y,Z,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
AB = []
for a in A:
    for b in B:
        AB.append(a+b)
AB.sort(reverse=True)
AB = AB[0:min(3001,X*Y*Z+1)]

ABC = []
for ab in AB:
    for c in C:
        ABC.append(ab+c)
ABC.sort(reverse=True)

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

### FIXED CODE ###

# 通ってるコードをコピペ、ほぼ同じはずなんだけどこれは通る？
x,y,z,k = map(int,input().split())
lisa = list(map(int,input().split()))
lisb = list(map(int,input().split()))
lisc = list(map(int,input().split()))
lisa.sort(reverse=True)
lisb.sort(reverse=True)
lisc.sort(reverse=True)
an = []
ans = []
for num in lisb:
    for nu in lisa:
        an.append(num+nu)
an.sort(reverse=True)
an = an[:min(3001,x*y*z+1)]
for num in lisc:
    for nu in an:
        ans.append(num+nu)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
### BUGGY CODE ###

import sys
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, (y-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def div(a, b):
    return mul(a, power(b, mod-2))

NNN = (10**5)
inverse = [0, 1]

for i in range( 2, NNN + 1 ):
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )


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

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

v2i = [0 for _ in range(N+1)]
def itt(v, p):
    cn = 0
    ms = []
    for u in G[v]:
        if u == p:
            continue
        un = itt(u, v)
        ms.append(un)
        cn += un
    if p != None:
        ms.append(N-1-cn)
    v2i[v] = ms
    return cn+1
itt(1, None)
r = 0
for v in range(1, N+1):
    ff = v2i[v]
    for f in ff:
        r += power(2, f) - 1 % mod
xx = power(2,N)
print((div(N, 2) - div(N+r, xx))%mod)


### FIXED CODE ###

import sys
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, (y-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def div(a, b):
    return mul(a, power(b, mod-2))

import sys
input = sys.stdin.readline


N = int(input())

d2 = [1]
inverse = [0, 1]
for _ in range(N):
    d2.append(2*d2[-1]%mod)
for i in range( 2,  10):
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )

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

v2i = [0 for _ in range(N+1)]
def itt(v, p):
    cn = 0
    ms = []
    for u in G[v]:
        if u == p:
            continue
        un = itt(u, v)
        ms.append(un)
        cn += un
    if p != None:
        ms.append(N-1-cn)
    v2i[v] = ms
    return cn+1
itt(1, None)
r = 0
for v in range(1, N+1):
    ff = v2i[v]
    for f in ff:
        r += d2[f] - 1 % mod
r = N*d2[N-1]-N-r
for _ in range(N):
    r = r*500000004 % mod
print(r)
### BUGGY CODE ###

N = int(input())
G = [[20 ** 9 for _ in range(N + 1)] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    G[a - 1][b - 1] = c
    G[b - 1][a - 1] = c
Q, K = map(int, input().split())

def dijkstra(s, N, G, g):
    d = [20 ** 9] * N
    used = [False] * N
    d[s] = 0

    while True:
        v = -1
        for i in range(N):
            if not used[i] and v == -1:
                v = i
            elif not used[i] and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True

        for i in range(N):
            d[i] = min(d[i], d[v] + G[v][i])
    
    return d[g]

dist = [0] * Q
for i in range(Q):
    x, y = map(int, input().split())
    dist[i] = dijkstra(x - 1, N, G, K - 1)
    dist[i] += dijkstra(K - 1, N, G, y - 1)

for d in dist:
    print(d)

### FIXED CODE ###

import heapq
N = int(input())
G = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    G[a - 1].append([c, b - 1])
    G[b - 1].append([c, a - 1])
Q, K = map(int, input().split())

def dijkstra(s, N, G):
    d = [float('inf')] * N
    d[s] = 0
    hq = [[0, s]]
    heapq.heapify(hq)
    while len(hq) > 0:
        v, i = heapq.heappop(hq)
        if d[i] < v:
            continue
        for c, j in G[i]:
            if d[j] > d[i] + c:
                d[j] = d[i] + c
                heapq.heappush(hq, [d[j], j])
    return d

D = dijkstra(K - 1, N, G)

dist = [0] * Q
for i in range(Q):
    x, y = map(int, input().split())
    dist[i] = D[x - 1] + D[y - 1]

for d in dist:
    print(d)
### BUGGY CODE ###

s,K = open(0).read().split()
K = int(K)
ss = set()
temp = set([''])
for x in s:
    t2 = set([''.join((y,x)) for y in temp])
    ss = ss | t2
    temp = t2.copy()
    temp.add('')
l = sorted(ss)
print(l[K-1])

### FIXED CODE ###

s,K = open(0).read().split()
K = int(K)
ss = set()
temp = set([''])
for x in s:
    temp = set([''.join((y,x)) for y in temp if len(y) <= 4])
    ss = ss | temp
    temp.add('')
l = list(ss)
l.sort()
print(l[K-1])
### BUGGY CODE ###

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

cnt =0
    
for r in range(N+1):
    
    for g in range(N+1-r*R):
        
        res = N- (r*R+g*G) 
        
        if  res >=0 and res%B ==0:
            cnt+=1
    
print(cnt)
            


### FIXED CODE ###

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

cnt =0
    
for r in range(int(N/R)+1):
  ball = N-r*R 
  for g in range(int(ball/G)+1):
    res = N- (r*R+g*G)
    if  res >=0 and res%B ==0:
      cnt+=1
    
print(cnt)
### BUGGY CODE ###

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

while True:
    c = c - b
    if c == 0:
        print('Yes')
        exit()
    
    a = a - d
    if a == 0:
        print('No')
        exit()

### FIXED CODE ###

import math

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

tkhs = math.ceil(c/b)
aok = math.ceil(a/d)

if tkhs <= aok:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

n, m = map(int, input().split())
MOD = 1000000007
a, b = n, m
count_n = n
count_m =m
count = 0
if abs(n-m) == 1:
  for _ in range(n-1):
    n -= 1
    count_n *= (n % MOD)
  for _ in range(m-1):
    m -= 1
    count_m *= (m % MOD)
  count = (count_m % MOD) * (count_n % MOD)
elif abs(n-m) == 0:
  for _ in range(n-1):
    n -= 1
    count_n *= (n % MOD)
  for _ in range(m-1):
    m -= 1
    count_m *= (m % MOD)
  count = 2 * (count_m % MOD) * (count_n % MOD)
  count %= MOD
else:
  count = 0

print(count)

### FIXED CODE ###

import math
n, m = map(int, input().split())
MOD = 1000000007
count_n = 0
count_m = 0
count = 0
if abs(n-m) == 1:
  count_n = math.factorial(n) % MOD
  count_m = math.factorial(m) % MOD
  count = count_m * count_n % MOD
elif abs(n-m) == 0:
  count_n = math.factorial(n) % MOD
  count_m = math.factorial(m) % MOD
  count = 2 * count_m * count_n % MOD
else:
  count = 0

print(count % MOD)