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

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

# 0 ~ 10**6
A_list = [True for i in range(10**6+1)]

# aのリストを作成
for i in a_l:
	for j in range(i*2, 10**6+1, i):
		A_list[j] = False

# Trueと一致するa_lの個数を数える
cnt = 0
for i in range(len(a_l)):
	if(a_l.count(a_l[i]) != 1):
		continue
	if(A_list[a_l[i]]):
		cnt += 1

print(cnt)

### FIXED CODE ###

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

# 0 ~ 10**6に入力値の個数を入れる
# (count()で数えると、o(n**2)になるため)
val_list = [0 for i in range(10**6+1)]
for i in a_l:
	val_list[i] += 1

# 重複削除
a_l = list(set(a_l))

# 0 ~ 10**6のリスト
A_list = [True for i in range(10**6+1)]
# 倍数のところにFalseを入れる
for i in a_l:
	for j in range(i*2, 10**6+1, i):
		A_list[j] = False

# Trueと一致するa_lの個数を数える
cnt = 0
for i in a_l:
	if(val_list[i] != 1):
		continue
	if(A_list[i]):
		cnt += 1

print(cnt)
### BUGGY CODE ###

n, k, q = map(int, input().split(' '))
p_list = [int(input()) for _ in range(q)]
scores = [k for _ in range(n)]
for p in p_list:
    for i in range(len(scores)):
        if i+1 != p:
            scores[i] -= 1
        else:
            pass

for s in scores:
    if s > 0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

n, k, q = map(int, input().split(' '))
p_list = [int(input()) for _ in range(q)]
scores = [k for _ in range(n)]
c_num = [0 for _ in range(n)]

if k > q:
    for _ in range(n):
        print('Yes')
else:
    for p in p_list:
        c_num[p-1] += 1
    for i in range(len(scores)):
        scores[i] -= q - c_num[i]
    for s in scores:
        if s > 0:
            print('Yes')
        else:
            print('No')
### BUGGY CODE ###

N = int(input())
S = input()
ans = 0
for i in range(10**3):
    s = str(i).zfill(3)
    flag = 0
    for j in range(N):
        if s[flag]==S[j]:
            flag += 1
            if flag == 3:
                break
    if flag==3:
        ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
ans = 0
for i in range(10**3):
    s = str(i).zfill(3)
    flag = 0
    for j in range(N):
        if s[flag]==S[j]:
            flag += 1
            if flag == 3:
                break
    if flag==3:
        ans += 1
print(ans)
### BUGGY CODE ###

D,G = map(int, input().split())
 
num_of_problems, complete_bonus = {},{}
 
for i in range(1, D+1):
    num_of_problems[i], complete_bonus[i] = map(int, input().split())
 
import itertools
 
min_num_of_solve = sum(num_of_problems.values())
 
for solve_order in itertools.permutations(num_of_problems.keys()): #解く順番を変えて総当り
    score_sum = 0
    num_of_solve = 0
 
    for j in range(len(solve_order)):
        for k in range(num_of_problems[solve_order[j]]):
            score_sum += solve_order[j]*100
            num_of_solve += 1
            if score_sum >= G:
                break
        
        score_sum += complete_bonus[solve_order[j]]
        if score_sum >= G:
            break
    min_num_of_solve = min(min_num_of_solve, num_of_solve)
    
print(min_num_of_solve)

### FIXED CODE ###

import numpy as np

D, G, *pc = map(int, open(0).read().split())
pc = list(zip(*[iter(pc)]*2))
p, c = np.array([]), np.array([])
for (x,y) in pc:
    p = np.append(p, x)
    c = np.append(c, y)
    
import numpy as np
import math

base_points = np.array([i*100 for i in range(1, D+1)])

ans = []

for i in range(2**D):
    bit_flag = np.array(list(map(int, format(i, '0%db' %D))))
    points = sum(bit_flag * (c + p*base_points))
    solved_num = sum(bit_flag * p)
    
    if points >= G:
        ans.append(solved_num)

    else:
        remained = G - points
        remained_problems = sorted((bit_flag==False) * np.array(range(1, D+1)), reverse=True)
        i = 0

        while True:
            if remained <= 0:
                break
                
            highest_p = remained_problems[i]

            if math.ceil(remained / (highest_p * 100)) <= p[highest_p - 1]:
                solved_num += math.ceil(remained / (highest_p * 100))
                remained -= (math.ceil(remained / (highest_p * 100)) * highest_p * 100)
            else:
                solved_num += p[highest_p - 1]
                remained -= (highest_p * 100 * p[highest_p - 1] + c[highest_p - 1])
                i += 1

        ans.append(solved_num)
        
print(int(min(ans)))
### BUGGY CODE ###

import math
N,M = list(map(int,input().split()))
A = [-1]+[int(input()) for _ in range(M)]+[N+1]
cnt = 0
ans = 1
for i in range(M+1):
  cnt = 0
  d = A[i+1]-A[i]-2
  for j in range(d//2+1):
    cnt += math.factorial(d-j)//(math.factorial(d-j*2)*math.factorial(j))
  ans *= cnt
print(ans%1000000007)

### FIXED CODE ###

N,M = map(int,input().split())
dp = [0]*(N+1)
dp[0] = 1
A=[int(input()) for _ in range(M)]
B=[1]*(N+1)
for i in range(M):
    B[A[i]] = 0
for i in range(N):
    if i-1 >= 0:
        dp[i+1] = dp[i]*B[i]+dp[i-1]*B[i-1]
    else:
        dp[i+1] = dp[i]*B[i]
    dp[i+1] %= 10**9+7
print(dp[N])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()

ans = 0
while a:
    st = 0
    if len(a)>1 and a[0] == a[1]:
        st = 1
    else:
        st = 0
        ans += 1
    a = [a[i] for i in range(st, len(a)) if a[i] % a[0] > 0]
print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = sorted(list(map(int, input().split())))
m = max(a)+1

numbers = [0] * m

for i in a:
    numbers[i] += 1

    if numbers[i] == 1:
        for j in range(2*i, m, i):
            numbers[j] += 2

print(numbers.count(1))
### BUGGY CODE ###

s = input()
ans = 0
def neg(c):
    if c == 'W':
        return 'B'
    else:
        return 'W'

while 'W' in s and 'B' in s:
    ans += 1
    l = s[0]
    r = s[-1]
    cl = 0
    cr = len(s) - 1
    while l == s[cl]:
        cl += 1
    while r == s[cr]:
        cr += -1
    if cr > cl:
        s = s[:cr] + (len(s) - cr + 1) * neg(r)
    else:
        s = (cl+1) * neg(l) + s[cl:]
print(ans)


### FIXED CODE ###

s = input()
n = len(s)

print(sum([ 1 for i in range(n-1) if s[i] != s[i+1]]))
### BUGGY CODE ###

n ,m = map(int, input().split())
result = set()
tmp = set()
first = True
for i in range(m):
    l, r = map(int, input().split())
    tmp = {i for i in range(l, r + 1)}
    if first:
        result = tmp
        first = False
    else:
        result = result.intersection(tmp)

print(len(result))

### FIXED CODE ###

n ,m = map(int, input().split())
L = []
R = []
for i in range(m):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)
if max(L) <= min(R):
    print(min(R) - max(L) + 1)
else:
    print(0)
### BUGGY CODE ###

N , M = map(int,input().split())
L = []
R = []
cnt = 0
flag = True
for i in range(M):
	l,r = map(int,input().split())
	L.append(l)
	R.append(r)
for i in range(N+1):
	flag = True
	for j in range(M):
		if i < L[j] or i > R[j]:
			flag = False
			break
	if flag == True:
		cnt+=1
print(cnt)

### FIXED CODE ###

N , M = map(int,input().split())
L = []
R = []
cnt = 0
flag = True
for i in range(M):
	l,r = map(int,input().split())
	L.append(l)
	R.append(r)
L_max = max(L)
R_min = min(R)
for i in range(N+1):
	flag = True
	if i >= L_max and i <= R_min:
		cnt+=1
print(cnt)
### BUGGY CODE ###

M=10**9+7
N=10**5*2
fac=[0]*(N+1)
fac[0]=b=1
for i in range(1,N+1):fac[i]=b=b*i%M
inv=[0]*(N+1)
inv[N]=b=pow(fac[N],M-2,M)
for i in range(N,0,-1):inv[i-1]=b=b*i%M
n,*t=open(0).read().split()
n=int(n)
e=[[]for _ in range(n)]
for a,b in zip(*[map(int,t)]*2):
    e[a-1]+=b-1,
    e[b-1]+=a-1,
o=[]
s=[0]
f=[1]*n
while s:
    v=s.pop()
    f[v]=0
    o+=v,
    l=[]
    for w in e[v]:
        if f[w]:
            l+=w,
            s+=w,
    e[v]=l
sz1,sz2=[0]*n,[0]*n
dp1,dp2=[0]*n,[0]*n
c=[[]for _ in range(n)]
for v in o[::-1]:
    s=b=1
    c1,c2=[1],[1]
    for w in e[v]:
        u=sz1[w]
        b=b*dp1[w]*inv[u]%M
        c1+=b,
        s+=u
    b=1
    for w in e[v][::-1]:
        b=b*dp1[w]*inv[sz1[w]]%M
        c2+=b,
    c[v]=c1,c2[::-1]
    sz1[v]=s
    dp1[v]=b*fac[s-1]%M
# print(dp1)
sz2[0]=1
dp2[0]=1
for v in o:
    l=len(e[v])
    c1,c2=c[v]
    uv=sz2[v]-1
    tv=dp2[v]*inv[uv]
    for i,w in enumerate(e[v]):
        tw=c1[i]*c2[i+1]%M
        uw=uv+sz1[v]-sz1[w]-1
        dp2[w]=tv*tw*fac[uw]%M
        sz2[w]=uw+2
# print(dp2)
a=[]
for dp1,dp2,sz1,sz2 in zip(dp1,dp2,sz1,sz2):
    sz1-=1
    sz2-=1
    a+=str(dp1*dp2*inv[sz1]*inv[sz2]*fac[sz1+sz2]%M),
print('\n'.join(a))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
M=10**9+7
N=10**6
fac=[0]*(N+1)
fac[0]=b=1
for i in range(1,N+1):fac[i]=b=b*i%M
inv=[0]*(N+1)
inv[N]=b=pow(fac[N],M-2,M)
for i in range(N,0,-1):inv[i-1]=b=b*i%M
def dfs1(v,p):
    s=1
    l=[]
    c1,c2=[1],[1]
    for w in e[v]:
        if w==p:continue
        l+=w,
        dfs1(w,v)
        u=sz1[w]
        c1+=c1[-1]*dp1[w]*inv[u]%M,
        s+=u
    for w in l[::-1]:
        c2+=c2[-1]*dp1[w]*inv[sz1[w]]%M,
    e[v]=l
    c[v]=c1,c2[::-1]
    sz1[v]=s
    dp1[v]=c1[-1]*fac[s-1]%M
n,*t=open(0).read().split()
n=int(n)
e=[[]for _ in range(n)]
for a,b in zip(*[map(int,t)]*2):
    e[a-1]+=b-1,
    e[b-1]+=a-1,
sz1,sz2=[0]*n,[0]*n
dp1,dp2=[0]*n,[0]*n
c=[[]for _ in range(n)]
dfs1(0,-1)
# print(dp1)
sz2[0]=1
dp2[0]=1
s=[0]
while s:
    v=s.pop()
    l=len(e[v])
    c1,c2=c[v]
    uv=sz2[v]-1
    tv=dp2[v]*inv[uv]
    for i,w in enumerate(e[v]):
        tw=c1[i]*c2[i+1]%M
        uw=uv+sz1[v]-sz1[w]-1
        dp2[w]=tv*tw*fac[uw]%M
        sz2[w]=uw+2
        s+=w,
# print(dp2)
for i in range(n):
    u1=sz1[i]-1
    u2=sz2[i]-1
    print(dp1[i]*dp2[i]*inv[u1]*inv[u2]*fac[u1+u2]%M)
### BUGGY CODE ###

N, S = map(int, input().split())
data = list(map(int, input().split()))

MOD = 998244353
dp = [[0]*(3001) for _ in range(N)]
ans = 0

for i, num in enumerate(data):
    dp[i][num] = 1
    for j in range(i):
        for k in range(3000-num, 0, -1):
            if dp[j][k] >= 1:
                dp[j][k+num] += dp[j][k]
            if k == num:
                dp[j][num] += 1
    for j in range(i+1):
        ans += dp[j][S]
    ans %= MOD

print(ans)

### FIXED CODE ###

P = 998244353

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

dp0 = [[0]*(S+1) for _ in range(N)]
dp1 = [[0]*(S+1) for _ in range(N)]
dp2 = [[0]*(S+1) for _ in range(N)]

dp0[0][0] = 1
dp1[0][0] = 1
if A[0] <= S:
    dp1[0][A[0]] = 1

for i in range(1, N):
    dp0[i][0] = 1
    dp1[i][0] = dp1[i-1][0] + 1
    dp2[i][S] = dp2[i-1][S] + dp1[i-1][S]
    if A[i] == S:
        dp2[i][S] += dp1[i-1][0] + 1
        dp1[i][S] += dp1[i-1][0] + 1
    elif A[i] < S:
        dp1[i][A[i]] += 1 + dp1[i-1][0]
    for j in range(1, S+1):
        dp1[i][j] += dp1[i-1][j]
        if j + A[i] < S:
            dp1[i][j+A[i]] += dp1[i-1][j]
        elif j + A[i] == S:
            dp2[i][S] += dp1[i-1][j]
            dp1[i][S] += dp1[i-1][j]
        dp0[i][j] %= P
        dp1[i][j] %= P
        dp2[i][j] %= P

print(dp2[N-1][S])
### BUGGY CODE ###

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

# A * B  = N - C
N = int(input())
count = 0
for i in range(1, N):
    AB = N - i
    count += len(make_divisors(AB))

print(count)

### FIXED CODE ###

N = int(input())

N_m1 = N - 1
counter = 0
for i in range(1, N_m1 + 1):
    counter += N_m1 // i

print(counter)
### BUGGY CODE ###

n,m,k=map(int,input().split())
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
uf=UnionFind(n)
arr=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int, input().split())
    uf.union(a-1,b-1)
    arr[a-1].append(b-1)
    arr[b-1].append(a-1)
for i in range(k):
    c,d=map(int, input().split())
    arr[c-1].append(d-1)
    arr[d-1].append(c-1)
ans=[0]*n
for i in range(n):
    print(len(list(set(uf.members(i))-set(arr[i])))-1)

### FIXED CODE ###

n,m,k=map(int,input().split())
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
uf=UnionFind(n)
arr=[0]*n
for i in range(m):
    a,b=map(int, input().split())
    uf.union(a-1,b-1)
    arr[a-1]+=1
    arr[b-1]+=1
for i in range(k):
    c,d=map(int, input().split())
    if uf.same(c-1,d-1):
        arr[c-1]+=1
        arr[d-1]+=1
for i in range(n):
    print(uf.size(i)-arr[i]-1)
### BUGGY CODE ###

from collections import deque
n, k = map(int, input().split())
inf = pow(10, 9)+7

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

not_yet = deque([0])
already = [False]*n
next_count = [0]*n

already[0] = True

ans = 1
while not_yet:
  key = not_yet.popleft()
  ans *= k-next_count[key]
  ans %= inf
  
  for value in tree[key]:
    next_count[value] += 1
    if not already[value]:
      not_yet.append(value)
      already[value] = True
    for value2 in tree[value]:
      next_count[value2] += 1

print(ans)

### FIXED CODE ###

from collections import deque
n, k = map(int, input().split())
inf = pow(10, 9)+7

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

not_yet = deque(tree[0])
already = [False]*n
already[0] = True
ans = k
key = k-1
for v in tree[0]:
  already[v] = True
  ans *= key
  ans %= inf
  key -= 1

while not_yet:
  key = not_yet.popleft()
  for v in range(k-2, k-1-len(tree[key]), -1):
    ans *= v
    ans %= inf
  
  for value in tree[key]:
    if already[value]:
      continue
    not_yet.append(value)
    already[value] = True

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

A, B, C, D = map(int, input().split())
result = 0
for i in range(B - A + 1):
    if((A + i)%C != 0 and (A + i)%D != 0):
      result += 1
print(result)

### FIXED CODE ###

import fractions
A, B, C, D = map(int, input().split())
Cdiv = B // C - (A - 1) // C
Ddiv = B // D - (A - 1) // D
gcd_CD = int(C * D / fractions.gcd(C, D))
CDdiv = B // gcd_CD - (A - 1) // gcd_CD
result = int(B - (A - 1) - Cdiv - Ddiv + CDdiv)
print(result)
### BUGGY CODE ###

import sys
import heapq
import operator as op

inf = float("inf")

def dijkstra(graph, start):
    dist = [inf for _ in range(len(graph))]
    dist[start] = 0
    prev = [None for _ in range(len(graph))]
    q = [(0, start)]
    rem = len(graph) - 1

    while q != [] and rem > 0:
        du, u = heapq.heappop(q)
        if dist[u] < du:
            continue
        rem -= 1

        for v, d in graph[u].items():
            if dist[v] > du + d:
                dist[v] = du + d
                prev[v] = u
                heapq.heappush(q, (dist[v], v))

    return dist, prev

n, m, s, t = map(int, next(sys.stdin).split(" "))

yen_graph = [dict() for _ in range(n)]
snuke_graph = [dict() for _ in range(n)]

for i in range(m):
    u, v, a, b = map(int, next(sys.stdin).split(" "))
    yen_graph[u-1][v-1] = yen_graph[v-1][u-1] = a
    snuke_graph[u-1][v-1] = snuke_graph[v-1][u-1] = b

yen_costs, _ = dijkstra(yen_graph, s-1)
snuke_costs, _ = dijkstra(snuke_graph, t-1)
total_costs = list(map(op.add, yen_costs, snuke_costs))

for i in range(n):
    print(10**15 - min(total_costs[i:]))


### FIXED CODE ###

import sys
from heapq import heappop, heappush
from itertools import accumulate
 
def dijkstra(n, edges, start, *, adj_matrix=False, default_value=float("inf")):
    inf = float("inf")
    vertices = [inf] * n
    vertices[start] = 0
    q, rem = [(0, start)], n - 1
 
    while q and rem:
        cost, v = heappop(q)
        if vertices[v] < cost:
            continue
        rem -= 1
 
        dests = ((i, n) for i, n in enumerate(edges[v]) if n != default_value)\
            if adj_matrix else edges[v]
 
        for dest, _cost in dests:
            newcost = cost + _cost
            if vertices[dest] > newcost:
                vertices[dest] = newcost
                heappush(q, (newcost, dest))
 
    return vertices
 
n, m, s, t = map(int, input().split())
s, t = s-1, t-1
yen = [[] for _ in [0]*n]
sno = [[] for _ in [0]*n]
for l in sys.stdin.readlines():
    u, v, a, b = map(int, l.strip().split())
    yen[u-1].append((v-1, a))
    yen[v-1].append((u-1, a))
    sno[u-1].append((v-1, b))
    sno[v-1].append((u-1, b))
 
yen = dijkstra(n, yen, s)
sno = dijkstra(n, sno, t)
result = list(accumulate([y+s for y, s in zip(yen, sno)][::-1], min))
money = 10**15
for n in result[::-1]:
    print(money-n)
### BUGGY CODE ###

def main():
    h,w = map(int,input().split())
    S = [[] for i in range(h)]
    q = []
    cnt = 0
    for i in range(h):
        s = input()
        for j in range(w):
            S[i].append(s[j])
            if s[j]=='#':
                q.append([i,j])
                cnt += 1
    ans = 0
    nxt = [(0,1),(1,0),(-1,0),(0,-1)]
    while cnt<h*w:
        q_ = []
        ans += 1
        while len(q)>0:
            b = q.pop(0)
            for nx in nxt:
                mv = [b[0]+nx[0],b[1]+nx[1]]
                if -1<mv[0]<h and -1<mv[1]<w:
                    if S[mv[0]][mv[1]]=='#':
                        continue
                    cnt += 1
                    S[mv[0]][mv[1]]='#'
                    q_.append(mv)
        q = q_
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import deque
def main():
    h,w = map(int,input().split())
    S = [list(input()) for i in range(h)]
    q = [(i,j) for i,a in enumerate(S) for j,b in enumerate(a) if b=='#']
    q = deque(q)
    ans = 0
    s = h*w
    cnt = len(q)
    nxt = [(0,1),(1,0),(-1,0),(0,-1)]
    while cnt < s:
        ans += 1
        q_ = deque([])
        while q:
            a,b = q.pop()
            for x,y in nxt:
                X,Y = a+x,b+y
                if 0>X or X>h-1 or 0>Y or Y>w-1:
                    continue
                if S[X][Y]=='.':
                    S[X][Y]='#'
                    q_.append((X,Y))
        q = q_
        cnt += len(q_)
    print(ans)

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

def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * 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 j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d


N = int(input())

cost = [[float("inf") for i in range(N)] for i in range(N)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    cost[a-1][b-1] = c
    cost[b-1][a-1] = c

Q, K = map(int, input().split())
    
ans = dijkstra(K-1, N, N-1, cost)
for i in range(Q):
    x, y = map(int, input().split())
    print(ans[x-1] + ans[y-1])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

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

dist = [-1] * N
def dfs(v, total_cost):
    # v：頂点, total_cost：今までかかったコストの合計
    dist[v] = total_cost
    for v_next, cost in tree[v]:
        if dist[v_next] >= 0:
            continue
            # v_nextが訪問済みならスキップ
        dfs(v_next, total_cost+cost)

dfs(K-1, 0)

for i in range(Q):
    x, y = map(int, input().split())
    print(dist[x-1] + dist[y-1])
### BUGGY CODE ###

N,M =map(int,input().split())
A = [0]*N
B = [0]*M
C = [0]*M
ans = int(0)

A = list(map(int, input().split()))
for i in range(M):
    B[i],C[i] = list(map(int,input().split()))

A.sort()

for i in range(M):
    j = int(0)
    while (j < B[i] and A[j]<C[i]) :
        A[j]=C[i]
        j +=1

    A.sort()

for i in range(N):
    ans += A[i]

print(ans)

### FIXED CODE ###

from heapq import heappush, heappop

# input
N,M =map(int,input().split())
A = [0]*N
B = [0]*M
C = [0]*M

A = list(map(int, input().split()))
A.sort()
for i in range(M):
    B[i],C[i] = list(map(int,input().split()))


def solve():

    pairs = zip(C, B)
    sortedpairs = sorted(pairs, key=lambda x: x[0])
    for i in range(M):
        B[i]=sortedpairs[i][1]
        C[i]=sortedpairs[i][0]

    ansA=[0]*N
    for j in range(N):
        ansA[j] = A[j]

    p = int(0)
    j = int(0)
    while  j<N and M>=1+p :
        jd = int(0)
        if ansA[j] >= C[M - 1 - p]:
            break
        while  B[M-1-p]-jd>0 :
            if j==N : break
            if ansA[j]>=C[M-1-p] :
                break
            else:
                ansA[j]=C[M-1-p]
            jd +=1
            j +=1

        p +=1

    ans = int(0)
    for j in range(N):
        ans += ansA[j]

    print(ans)

solve()
### BUGGY CODE ###

n,*a=map(int,open(0).read().split())
for i in range(n):
  b=a[:]
  b.pop(i)
  print(max(b))

### FIXED CODE ###

n,*a=map(int,open(0).read().split())
b=sorted(a)
for i in range(n):
  print(b[-1] if a[i]!=b[-1] else b[-2])
### BUGGY CODE ###

N,Q = map(int , input().split())
S = input()
lr = [list(map(int, input().split())) for _ in range(Q)]

# print(N, Q)
# print(S)
# print(lr)

for i in lr:
  print(S[i[0]-1:i[1]].count('AC'))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)
for i in range(N):
  t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
  l, r = map(int, input().split())
  print(t[r-1] - t[l-1])