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

import sys
import numpy as np

def main():

	input = sys.stdin.readline

	N = int(input().strip())
	P = np.array(list(map(int,input().strip().split())))

	ips = np.argsort(P)[::-1]
	psort = np.sort(P)[::-1]

	x = 0
	largeind = [-1,-1,N,N]
	for i in range(N):
		target = ips[i]

		larger = len(largeind)-2
		smaller = 1
		while larger-smaller!=1:
			medium = int((larger+smaller)/2)
			if largeind[medium]>target:
				larger = medium
			else:
				smaller = medium
		largeind.insert(larger,target)

		L1ind = largeind[larger-1]
		L2ind = largeind[larger-2]
		R1ind = largeind[larger+1]
		R2ind = largeind[larger+2]

		x += ((L1ind-L2ind)*(R1ind-target) + (target-L1ind)*(R2ind-R1ind))*psort[i]

	print(x)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

def main():

	input = sys.stdin.readline

	N = int(input().strip())
	P = list(map(int,input().strip().split()))

	RR = [i+1 for i in range(N)]
	LL = [i-1 for i in range(N)]
	ips = [0]*(N)
	for i, val in enumerate(P):
		ips[val-1] = i
	P.sort()

	x = 0
	for i in range(N):
		target = ips[P[i]-1]
		R1ind = RR[target]
		R2ind = RR[ min(R1ind,N-1) ]
		L1ind = LL[target]
		L2ind = LL[ max(L1ind,0) ]

		x += ((L1ind-L2ind)*(R1ind-target) + (target-L1ind)*(R2ind-R1ind))*P[i]

		if L1ind!=-1:
			RR[L1ind] = R1ind
		if R1ind!=N:
			LL[R1ind] = L1ind

	print(x)

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

N = int(input())
input = [int(s) for s in input().split()]
ans = 0
for i in range(N-1):
    ans = ans + input[i]*sum(input[i+1:])

print(ans%(10**9+7))

### FIXED CODE ###

N = int(input())
input = [int(s) for s in input().split()]
ans = 0
temp=sum(input)
for i in range(N-1):
    temp=temp-input[i]
    ans = (ans + (input[i]*((temp)%(10**9+7)))%(10**9+7))%(10**9+7)
print(ans)
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in 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[:min(3001, X * Y * Z + 1)]
ABC = []
for ab in AB:
  for c in C:
    ABC.append(ab + c)
ABC.sort(reverse=True)
print(*ABC[:K], sep='\n')


### FIXED 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[:min(3001, X * Y * Z + 1)]
ABC = []
for c in C:
  for ab in AB:
    ABC.append(ab + c)
ABC.sort(reverse=True)
for i in range(K):
  print(ABC[i])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(K: int):

    ct = 0
    q = [1,2,3,4,5,6,7,8,9]
    while(len(q)>0):
        a = q.pop(0)
        al = a % 10
        ct += 1 
        if ct == K:
            print(a)
            break

        if al != 0:
            q += [a*10+al - 1]
        q += [a*10+al]
        if al != 9:
            q += [a*10+al + 1]

        # print(q)


    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    solve(K)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import deque

def solve(K: int):

    ct = 0
    q = deque([1,2,3,4,5,6,7,8,9])
    while(len(q)>0):
        a = q.popleft()
        al = a % 10
        ct += 1 
        if ct == K:
            print(a)
            break

        if al != 0:
            q.append(a*10+al - 1)
        q.append(a*10+al)
        if al != 9:
            q.append(a*10+al + 1)

        # print(q)


    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    solve(K)

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

from collections import deque

n,m = map(int,input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
ans = 1

def dfs(node):
    while len(todo) > 0:
        node = todo.pop()
        if tf[node] == 0:
            tf[node] = 1
            seen.add(node)
            for nextnode in graph[node]:
                todo.append(nextnode)

todo = deque()
done = set()
for i in range(1,n+1):
    if i in done:
        continue
    else:
        todo.append(i)
        tf = [0 for _ in range(n+1)]
        seen = set()
        dfs(i)
        ans = max(ans,len(seen))
        done |= seen
print(ans)

### FIXED CODE ###

from collections import deque

n,m = map(int,input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
ans = 1

def dfs(node):
    while len(todo) > 0:
        node = todo.pop()
        if tf[node] == 0:
            tf[node] = 1
            seen.add(node)
            for nextnode in graph[node]:
                todo.append(nextnode)

todo = deque()
done = set()
tf = [0 for _ in range(n+1)]
for i in range(1,n+1):
    if i in done:
        continue
    else:
        todo.append(i)
        seen = set()
        dfs(i)
        #print(i,seen)
        ans = max(ans,len(seen))
        done |= seen
print(ans)
### BUGGY CODE ###

def solve():
    H,W = map(int,input().split())
    A = [list(map(int,input().split())) for _ in range(H)]
    B = [list(map(int,input().split())) for _ in range(H)]
    D = [[abs(A[h][w]-B[h][w]) for w in range(W)] for h in range(H)]
    dp = [[{} for _ in range(W)] for _ in range(H)]
    dp[0][0][D[0][0]] = 0
    for h in range(H):
        for w in range(W):
            for v in dp[h][w]:
                if w != W-1:
                    v1 = v+D[h][w+1]
                    v2 = v-D[h][w+1]
                    if v1<0:
                        v1 *= -1
                    if v2<0:
                        v2 *= -1
                    dp[h][w+1][v1] = 0
                    dp[h][w+1][v2] = 0
                if h != H-1:
                    v1 = v+D[h+1][w]
                    v2 = v-D[h+1][w]
                    if v1<0:
                        v1 *= -1
                    if v2<0:
                        v2 *= -1
                    dp[h+1][w][v1] = 0
                    dp[h+1][w][v2] = 0
    ans = min(dp[H-1][W-1])
    return ans
print(solve())

### FIXED CODE ###

H,W = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(H)]
B = [list(map(int,input().split())) for _ in range(H)]
D = [[abs(A[h][w]-B[h][w]) for w in range(W)] for h in range(H)]
def cal():
    dp1 = [set() for _ in range(W)]
    dp2 = [set() for _ in range(W)]
    for h in range(H):
        for w in range(W):
            d = D[h][w]
            if h==0 and w==0:
                dp2[0].add(d)
            for v in dp1[w]:
                v1 = v+d
                v2 = v-d if v>=d else -v+d
                dp2[w].add(v1)
                dp2[w].add(v2)
            if 0 < w:
                for v in dp2[w-1]:
                    v1 = v+d
                    v2 = v-d if v>=d else -v+d
                    dp2[w].add(v1)
                    dp2[w].add(v2)
        dp1 = dp2
        dp2 = [set() for _ in range(W)]
    return min(dp1[W-1])
ans = cal()
print(ans)
### BUGGY CODE ###

# 組み合わせを全て考える
# タイムアウトになった
N = int(input())
S = input()
L = []
import itertools
seq = [i for i in range(N)]
combi = list(itertools.combinations(seq,3))
for c in combi:
    x = [S[j] for j in c]
    L.append("".join(x))
print(len(set(L)))

### FIXED CODE ###

def solve():
    ans = 1
    N = int(input())
    s = input()
    ans = 0
    for i in range(1000):
        t = str(i).zfill(3)
        t_index = 0 
        for s_index in range(N):
            if s[s_index] == t[t_index]:
                t_index += 1
                if t_index == 3:
                    break
        if t_index == 3:
            ans += 1
    print(ans)
solve()
### BUGGY CODE ###

import bisect

def solve():
    N, Q = [int(_) for _ in raw_input().split()]
    STX = []
    for i in range(N):
        Si, Ti, Xi = [int(_) for _ in raw_input().split()]
        STX.append((Si - Xi, Ti - Xi, Xi))
    D = []
    for i in range(Q):
        D.append((int(raw_input()), i))
    STX.sort(key = lambda x:x[2], reverse=True)
    # D have already been sorted based on settings on problem
    ans = [-1] * Q
    for i in range(N):
        Li, Ri, Xi = STX[i]
        lit = bisect.bisect_left(D, (Li, -1))
        rit = bisect.bisect_left(D, (Ri, -1))
        while lit < rit:
            ans[D[lit][1]] = Xi
            lit += 1
    for i in range(Q):
        print ans[i]

if __name__ == '__main__':
    solve()


### FIXED CODE ###

import bisect

def solve():
    N, Q = [int(_) for _ in raw_input().split()]
    STX = []
    for i in range(N):
        Si, Ti, Xi = [int(_) for _ in raw_input().split()]
        STX.append((Si - Xi, Ti - Xi, Xi))
    D = []
    for i in range(Q):
        D.append((int(raw_input()), i))
    STX.sort(key = lambda x:x[2])
    # D have already been sorted based on settings on problem
    ans = [-1] * Q
    l = [None] * Q
    for i in range(N):
        Li, Ri, Xi = STX[i]
        lit = bisect.bisect_left(D, (Li, -1))
        rit = bisect.bisect_left(D, (Ri, -1))
        while lit < rit:
            if l[lit] is not None:
                lit = l[lit]
            else:
                ans[D[lit][1]] = Xi
                l[lit] = rit
                lit += 1
    for i in range(Q):
        print ans[i]

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


N=int(input())

X=[]
for x in range(N):
    X.append(int(input()))

result=[]
Y=[]
for i in range(len(X)):
    Y=X[:]
    Y.pop(i)
    result.append(max(Y))

for x in result:
    print(x)

### FIXED CODE ###

import numpy as np

N=int(input())

X=[]
for x in range(N):
    X.append(int(input()))

Y=[]
Y=np.sort(X)[::-1]

for i in range(N):
    ans=Y[0]
    if ans==X[i]:
        ans=Y[1]
    print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
l = []
for i in range(n):
    l.append(int(input()))

root = [1]*n

for i in range(n)[-2::-1]:
    num = 0
    for j in range(i + 1, i + 500):
        if j >= n:
            break
        if abs(l[i] - l[j]) <= k:
            num = max(num, root[j])
    root[i] += num

print(max(root))

### FIXED CODE ###

n, k = map(int, input().split())
l = []
for i in range(n):
    l.append(int(input()))

root = [1]*n

for i in range(n)[-2::-1]:
    num = 0
    for j in range(i + 1, i + 200):
        if j >= n:
            break
        if abs(l[i] - l[j]) <= k:
            num = max(num, root[j])
    root[i] += num

print(max(root))
### BUGGY CODE ###

from collections import deque

def main():
    N, X, Y = map(int, input().split())
    ans = {i: 0 for i in range(1, N)}
    for i in range(1, N + 1):
        cost = [-1]*(N+1)
        cost[i] = 0
        d = deque([i])
        while len(d) != 0:
            v = d.popleft()
            c = cost[v]
            for j in [-1, 1]:
                vj = v + j
                if vj > 0 and vj <= N and cost[vj] == -1:
                    cost[vj] = c + 1
                    d.append(vj)
                    ans[c + 1] += 1
            if v in [X, Y]:
                vxy = X + Y - v
                if cost[vxy] == -1:
                    cost[vxy] = c + 1
                    d.append(vxy)
                    ans[c + 1] += 1
    for a in ans:
        print(ans[a]//2)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import deque

def main():
    N, X, Y = map(int, input().split())
    ans = {i: 0 for i in range(1, N)}
    for i in range(1, N + 1):
        cost = [-1]*(N+1)
        cost[i] = 0
        d = deque([i])
        while len(d) != 0:
            v = d.popleft()
            c = cost[v]
            for j in [-1, 1]:
                vj = v + j
                if vj > 0 and vj <= N and cost[vj] == -1:
                    cost[vj] = c + 1
                    d.append(vj)
                    ans[c + 1] += 1
            if v in [X, Y]:
                vxy = X + Y - v
                if cost[vxy] == -1:
                    cost[vxy] = c + 1
                    d.append(vxy)
                    ans[c + 1] += 1
    for a in ans:
        print(ans[a]//2)


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

a,b = map(int, input().split())
i = max(a,b)
s = 0
while(i <= a*b):
    if (i%a == 0 and i%b == 0):
        s = i
        break
    i += 1
print(i)

### FIXED CODE ###

a,b = map(int, input().split())
i = min(a,b)
s = 0
while(i <= a*b):
    if (i%a == 0 and i%b == 0):
        s = i
        break
    i += min(a,b)
print(i)
### BUGGY CODE ###

import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

R,C,K = LI()
r,c,v = LIR(K,3)

a = [[0]*C for _ in range(R)]
for i in range(K):
    a[r[i]-1][c[i]-1] = v[i]

dp = [[[0]*4 for _ in range(C)] for _ in range(R)]
if a[0][0]:
    dp[0][0][1] = a[0][0]

for i in range(R):
    for j in range(C):
        upper_max = max(dp[i-1][j]) if i >= 1 else 0
        for k in range(4):
            if i == j == 0:
                continue
            val1 = 0
            val2 = 0
            val3 = 0
            val4 = 0
            if j >= 1:
                val1 = dp[i][j-1][k]
            if k == 0 and i >= 1:
                val2 = upper_max
            if a[i][j] != 0:
                if k == 1 and i >= 1:
                    val3 = upper_max + a[i][j]
                if k >= 1 and j >= 1:
                    val4 = dp[i][j-1][k-1] + a[i][j]
            dp[i][j][k] = max(val1,val2,val3,val4)

print(max(dp[R-1][C-1]))

### FIXED CODE ###

import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

R,C,K = LI()
r,c,v = LIR(K,3)

def index(i,j,k):
    return k*C*R + i*C + j

a = [[0]*C for _ in range(R)]
for i in range(K):
    a[r[i]-1][c[i]-1] = v[i]

dp = [0]*(4*C*R)
dp[index(0,0,1)] = a[0][0]

for i in range(R):
    for j in range(C):
        if i == j == 0:
            continue
        upper_max = 0
        if i >= 1:
            for k in range(4):
                upper_max = max(upper_max,dp[index(i-1,j,k)])
        for k in range(4):
            val1 = 0
            val2 = 0
            val3 = 0
            val4 = 0
            if j >= 1:
                val1 = dp[index(i,j-1,k)]
            if k == 0 and i >= 1:
                val2 = upper_max
            if a[i][j] != 0:
                if k == 1 and i >= 1:
                    val3 = upper_max + a[i][j]
                if k >= 1 and j >= 1:
                    val4 = dp[index(i,j-1,k-1)] + a[i][j]
            dp[index(i,j,k)] = max(val1,val2,val3,val4)

ans = 0
for k in range(4):
    ans = max(ans,dp[index(R-1,C-1,k)])

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

import sys

n = int(input())

dct = []

for line in sys.stdin:

    cmd, val = line.strip().split()

    if cmd == 'insert':
        dct.append(val)

    else:
        if val in dct:
            print('yes')
        else:
            print('no')



### FIXED CODE ###

import sys

htable = [0] * 16777216


def to_int(s):
    if s == 'A':
        return 1
    elif s == 'C':
        return 2
    elif s == 'G':
        return 3
    else:
        return 4


def to_hash(string):
    h = 0
    for i, s in enumerate(string):
        ints = to_int(s)
        h += 4**i * ints

    return h


def insert(string):
    h = to_hash(string)
    htable[h] = 1


def find(string):
    h = to_hash(string)
    if htable[h]:
        print('yes')
    else:
        print('no')


if __name__ == '__main__':

    n = int(input())

    for line in sys.stdin:
        cmd, string = line.strip().split()

        if cmd == 'insert':
            insert(string)

        else:
            find(string)
### BUGGY CODE ###

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

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H,W=MAP()

que = deque()
# 右左上下
directions = [(0,1),(0,-1),(1,0),(-1,0)]
# 四方に一回り大きいグリッドを作る
grid = list2d(H+2, W+2, '*')
for i in range(1,H+1):
    row = list(input())
    for j in range(1, W+1):
        grid[i][j] = row[j-1]
        if grid[i][j]=='#':
            que.append((i, j))

cnt=0
while len(que) != 0:
    ln=len(que)
    for i in range(ln):
        cur=que.popleft()
        # 4方向見る
        for direction in directions:
            nxt = list(map(lambda x,y: x+y, cur, direction))
            # 壁と黒はスキップ
            if grid[nxt[0]][nxt[1]]=='*' or grid[nxt[0]][nxt[1]]=='#':
                continue
            # 白を埋める
            if grid[nxt[0]][nxt[1]]=='.':
                grid[nxt[0]][nxt[1]]='#'
                que.append(nxt)
    cnt+=1
print(cnt-1)


### FIXED CODE ###

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

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H,W=MAP()

que = deque()
# 右左上下  
directions = [(0,1),(0,-1),(1,0),(-1,0)]
# 四方に一回り大きいグリッドを作る
grid = list2d(H+2, W+2, '*')
for i in range(1,H+1):
    row = list(input())
    for j in range(1, W+1):
        grid[i][j] = row[j-1]
        if grid[i][j] == '#':
            que.append((i, j, 0))

# 移動距離メモ
memo=[[-1]*(W+2) for i in range(H+2)]
while len(que):
    cur=que.popleft()
    if memo[cur[0]][cur[1]]!=-1:
        continue
    memo[cur[0]][cur[1]]=cur[2]
    # 4方向見る
    for direction in directions:
        x=cur[0]+direction[0]
        y=cur[1]+direction[1]
        # 壁と黒はスキップ
        if grid[x][y]=='*' or grid[x][y]=='#':
            continue
        # 白を埋める
        if grid[x][y]=='.':
            grid[x][y]='#'
            que.append((x, y, cur[2]+1))
ans=0
for i in range(1, H+1):
        ans=max(ans, max(memo[i]))
print(ans)
### BUGGY CODE ###

import sys

n, m = map(int, sys.stdin.readline().split())
A = [int(sys.stdin.readline()) for _ in range(m)]

dp = [0 for i in range(n+1)]
dp[0] =1
#print(dp)

for i in range(1, n+1):
    if i in A:
        continue
    if i-2>=0:
        dp[i] = dp[i-1] + dp[i-2]
    else:
        dp[i] = dp[i-1]


print(dp[-1]%1000000007)

### FIXED CODE ###

import sys

n, m = map(int, sys.stdin.readline().split())
A = [int(sys.stdin.readline()) for _ in range(m)]
bloken = [0 for i in range(n+1)]
for a in A:
    bloken[a]=1
    

dp = [0 for i in range(n+1)]
dp[0] =1
#print(dp)

for i in range(1, n+1):
    if bloken[i]==1:
        continue
    if i-2>=0:
        dp[i] = dp[i-1] + dp[i-2]
    else:
        dp[i] = dp[i-1]


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

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

from heapq import heappop, heappush

def dijkstra(E, start):
    N_d = len(E)
    dist = [INF] * N_d
    dist[start] = 0
    q = [(0, start)]
    while q:
        dist_v, v = heappop(q)
        if dist[v] != dist_v:
            continue
        for u, dist_vu in E[v]:
            dist_u = dist_v + dist_vu
            if dist_u < dist[u]:
                dist[u] = dist_u
                heappush(q, (dist_u, u))
    return dist

N = INT()
abc = [LIST() for i in range(N-1)]
Q, K = MAP()
xy = [LIST() for i in range(Q)]

graph = defaultdict(list)

for a, b, c in abc:
    graph[a-1].append((b-1, c))
    graph[b-1].append((a-1, c))

    # graph[a-1].append((b-1, c))

# print(dijkstra(graph, 1))
for x, y in xy:
    ans = dijkstra(graph, x-1)[K-1] + dijkstra(graph, K-1)[y-1]
    print(ans)


### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

from heapq import heappop, heappush

def dijkstra(E, start):
    N_d = len(E)
    dist = [INF] * N_d
    dist[start] = 0
    q = [(0, start)]
    while q:
        dist_v, v = heappop(q)
        if dist[v] != dist_v:
            continue
        for u, dist_vu in E[v]:
            dist_u = dist_v + dist_vu
            if dist_u < dist[u]:
                dist[u] = dist_u
                heappush(q, (dist_u, u))
    return dist

N = INT()
abc = [LIST() for i in range(N-1)]
Q, K = MAP()
xy = [LIST() for i in range(Q)]

graph = defaultdict(list)

for a, b, c in abc:
    graph[a-1].append((b-1, c))
    graph[b-1].append((a-1, c))

    # graph[a-1].append((b-1, c))

d = dijkstra(graph, K-1)

for x, y in xy:
    # ans = dijkstra(graph, x-1)[K-1] + dijkstra(graph, K-1)[y-1]
    # d = dijkstra(graph, K-1)
    
    ans = d[x-1] + d[y-1]
    # dijkstra(graph, x-1)
    print(ans)