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

#!/usr/bin/env python3
import sys, math, itertools, heapq, collections, bisect,copy
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**7)
inf = float('inf')
mod = 10**9+7
ans = inf ;count = 0 ;pro = 1

h,w=map(int,input().split())
A=[tuple(map(int,input().split())) for i in range(h)]
B=[tuple(map(int,input().split())) for i in range(h)]
a=[set() for j in range(w)]
dp=[copy.deepcopy(a) for i in range(h)]
dp[0][0].add(abs(A[0][0]-B[0][0]))
for i in range(h):
    for j in range(w):
        d=abs(A[i][j]-B[i][j])
        if i-1>=0:
            for si in dp[i-1][j]:
                if si+d<=6500:
                    dp[i][j].add(si+d)
                if abs(si-d)<=6500:
                    dp[i][j].add(abs(si-d))
        if j-1>=0:
            for si in dp[i][j-1]:
                if si+d <= 6500:
                    dp[i][j].add(si+d)
                if abs(si-d) <= 6500:
                    dp[i][j].add(abs(si-d))
ans=min(dp[h-1][w-1])
print(ans)
# for di in dp:
#     print(di)



### FIXED CODE ###

#!/usr/bin/env python3
import sys, math, itertools, heapq, collections, bisect,copy
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**7)
inf = float('inf')
mod = 10**9+7
ans = inf ;count = 0 ;pro = 1

h,w=map(int,input().split())
A=[tuple(map(int,input().split())) for i in range(h)]
B=[tuple(map(int,input().split())) for i in range(h)]
# a=[set() for j in range(w)]
K=160*80
dp = [[0]*w for i in range(h)]
dp[0][0]=1<<K
for i in range(h):
    for j in range(w):
        d=abs(A[i][j]-B[i][j])
        if i-1>=0:
            dp[i][j] |= dp[i-1][j]
        if j-1>=0:
            dp[i][j] |= dp[i][j-1]
        dp[i][j] = (dp[i][j]<<d) | (dp[i][j]>>d)


ans = K
for i in range(2*K):
    if dp[h-1][w-1]  & (1 << i)>0:
        ans = min(ans,abs(K-i))
print(ans)
# for di in dp:
#     print(di)
### BUGGY CODE ###

import sys

input = sys.stdin.readline

def main():
    ans = 0
    H, W, M = map(int, input().split())
    bombs = []
    hs = [0]*(H+1)
    ws = [0]*(W+1)
    for _ in range(M):
        h, w = map(int, input().split())
        bombs.append([h, w])
        hs[h] += 1
        ws[w] += 1
    maxh = max(hs)
    maxw = max(ws)
    ans = maxh + maxw

    maxwindex = [i for i, x in enumerate(ws) if x == maxw]

    isfound = False

    for i in range(H):
        if isfound:
            break
        if hs[i+1] == maxh:
            for j in maxwindex:
                if [i+1, j] not in bombs:
                    isfound = True
                    break
    if isfound == False:
        ans -= 1

    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys

input = sys.stdin.readline

def main():
    ans = 0
    H, W, M = map(int, input().split())
    bombs = []
    hs = [0]*(H)
    ws = [0]*(W)
    for _ in range(M):
        h, w = map(int, input().split())
        bombs.append(tuple([h-1, w-1]))
        hs[h-1] += 1
        ws[w-1] += 1
    maxh = max(hs)
    maxw = max(ws)
    ans = maxh + maxw

    maxhindex = [i for i, x in enumerate(hs) if x == maxh]
    maxwindex = [i for i, x in enumerate(ws) if x == maxw]

    isfound = False

    bombs = set(bombs)
    for i in maxhindex:
        for j in maxwindex:
            if (i, j) not in bombs:
                print(ans)
                exit()

    print(ans-1)

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

n,m=map(int,input().split())
lis=[]
ng=[set() for _ in range(n)]

for i in range(m):
    A,B=map(int,input().split())
    lis.append([A,B])
    ng[A].add(B)
    
lis.sort()
now=[]
danger=set()
cu=0
for i in range(1,n):
    now.append(i)
    danger=danger|ng[i]
    if(i+1 in danger):
        cu+=1
        danger=set()
            
print(cu)

### FIXED CODE ###

n,m=map(int,input().split())
ng=[set() for _ in range(n)]

for i in range(m):
    A,B=map(int,input().split())
    ng[A].add(B)
    
now=[]
danger=set()
cu=0
for i in range(1,n):
    now.append(i)
    for j in ng[i]:
        danger.add(j)
    if(i+1 in danger):
        cu+=1
        danger.clear()
            
print(cu)
### BUGGY CODE ###

import itertools
N, C = map(int, input().split())
X = []
V = []
for n in range(N):
    x, v = map(int,input().split())
    X.append(x)
    V.append(v)
X_r = X[::-1]
V_r = V[::-1]
X = [0] + X
V = [0] + V
X_r = [0] + [C-x for x in X_r]
V_r = [0] + V_r

#cx = list(itertools.accumulate(X))
cv = list(itertools.accumulate(V))
#cxr = list(itertools.accumulate(X_r))
cvr = list(itertools.accumulate(V_r))

# print (X)
# print (X_r)
# print (cv)
# print (cvr)

# L = []
# for i in range(N+1):
#     L.append(cv[i]-X[i])
# R = []
# for i in range(N+1):
#     R.append(cvr[i]-X_r[i])

# print (L,R)
mx = 0
for l in range(N+1):
    for r in range(N+1-l):
        #print (l,r)
        a = -2*X[l]+cv[l]+cvr[r]-X_r[r]
        mx = max(mx,a)
        a = -2*X_r[l]+cv[r]+cvr[l]-X[r]
        mx = max(mx,a)
print (mx)

### FIXED CODE ###

import itertools
N, C = map(int, input().split())
X = []
V = []
for n in range(N):
    x, v = map(int,input().split())
    X.append(x)
    V.append(v)
Xr = X[::-1]
Vr = V[::-1]
Xl = [0] + X
Vl = [0] + V
Xr = [0] + [C-x for x in Xr] # 逆に回るのでCから引く
Vr = [0] + Vr

Vl = list(itertools.accumulate(Vl)) # xは累積した値なので、vも累積和に統一
Vr = list(itertools.accumulate(Vr))

def update_mx(ls):
    mx = 0
    for i in range(len(ls)):
        mx = max(mx, ls[i])
        ls[i] = mx
    return ls

def create(V,X,k):
    ls = []
    for n in range(N+1):
        ls.append(V[n]-k*X[n]) # 往復する場合はk=2
    return update_mx(ls)

L = create(Vl,Xl,1) # 最良の値[左端として許容される位置]（片道）
Lt = create(Vl,Xl,2) # 最良の値[左端として許容される位置]（往復）
R = create(Vr,Xr,1)
Rt = create(Vr,Xr,2)

ans = 0
for n in range(N+1):
    #print (n,N-n)
    ans = max(ans, Lt[n] + R[N-n])
    ans = max(ans, Rt[n] + L[N-n])
print (ans)
### BUGGY CODE ###

n,m = list(map(int,input().split()))
counter = 0
data = []
checkd = []
tmp = {}

wa = 0
#入力処理
for i in range(m):
  a,b = input().split()
  if b == "WA":
    if int(a) not in tmp:
      tmp[int(a)] = 0
    tmp[int(a)] += 1  
  elif (( b == "AC") and (int(a)) not in checkd):
    counter += 1
    checkd.append(int(a))
    if int(a) not in tmp:
      tmp[int(a)] = 0  
    wa += tmp[int(a)]


"""
for i in range(m):
  if data[i][1] == "WA":
    if int(data[i][0]) not in tmp:
      tmp[int(data[i][0])] = 0
    tmp[int(data[i][0])] += 1  
  elif ((data[i][1]) == "AC") and (int(data[i][0]) not in checkd):
    counter += 1
    checkd.append(int(data[i][0]))
    if int(data[i][0] ) not in tmp:
      tmp[int(data[i][0])] = 0  
    wa += tmp[int(data[i][0])]
"""    
print(counter,wa)

  
  



### FIXED CODE ###

n,m = list(map(int,input().split()))
counter = 0
data = []
tmp = {}#問題番号をkeyとしてWAをカウント

wa = 0
#入力処理
for _ in range(m):
  a,b = input().split() #入力処理
  if b == "WA": #解答がWA→tmpに問題番号をkeyとしてカウント
    if int(a) not in tmp:
      tmp[int(a)] = 0
    if tmp[int(a)] != -1:
      tmp[int(a)] += 1
  if int(a) not in tmp: #WA無しのACの対応 
    tmp[int(a)] = 0
  if (( b == "AC") and (tmp[int(a)] != -1)):#解答がACでtmp[問題番号]が出力済みでない場合
    counter += 1
    #checkd.append(int(a))
    wa += tmp[int(a)] #問題番号aの値をWAの合計に加算
    tmp[int(a)] = -1 #問題番号aが加算済み


"""
for i in range(m):
  if data[i][1] == "WA":
    if int(data[i][0]) not in tmp:
      tmp[int(data[i][0])] = 0
    tmp[int(data[i][0])] += 1  
  elif ((data[i][1]) == "AC") and (int(data[i][0]) not in checkd):
    counter += 1
    checkd.append(int(data[i][0]))
    if int(data[i][0] ) not in tmp:
      tmp[int(data[i][0])] = 0  
    wa += tmp[int(data[i][0])]
"""    
print(counter,wa)
### BUGGY CODE ###

import itertools
n = int(input())
a = list(map(int, input().split()))
suf = list(itertools.combinations(range(n), 2))
total = 0
mod = 10**9 + 7
for i, j in suf:
    # print(i, j)
    total = (total + (a[i] * a[j]) % mod) % mod
print(total)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = [0] * n
b[-1]= a[-1]
total = 0
mod = 10**9 + 7
for i in range(n-2, 0, -1):
    b[i] = a[i] + b[i + 1]
for i in range(n-1):
    total = (total + (a[i] * b[i + 1]) % mod) % mod
print(total)
### BUGGY CODE ###

import numpy as np

N = int(input())

a = list(map(int, input().split()))
A = np.array([a for i in range(N)])
B = np.array([[a[i]] * N for i in range(N)])
C = A + B
ind = np.array([[i-j for i in range(N)] for j in range(N)])

D = C - ind
cnt = np.count_nonzero(D == 0)
print(cnt)

### FIXED CODE ###

import collections

N = int(input())
A = list(map(int, input().split()))
B = collections.defaultdict(int)
C = collections.defaultdict(int)

for i in range(N):
    B[i-A[i]] += 1 
    C[i+A[i]] += 1
#print(B)
#print(C)
ans = 0
for i in B:
    #print(i) i=Key
    if i in C:
        ans += B[i]*C[i]
print(ans)
### BUGGY CODE ###

n, s = [int(i) for i in  raw_input().split()]
weights = []
values = []

for _ in range(n):
    w, v = [int(i) for i in raw_input().split()]
    weights.append(w)
    values.append(v)

def knapsack(weights, values, limit):
    n = len(weights)
    f = [[0 for _ in range(limit+1)] for _ in range(n)]

    if weights[0] <= limit:
        for w in range(weights[0], limit+1):
            f[0][w] = values[0]

    for w in range(1, limit+1):
        for i in range(1, n):
            f[i][w] = max(f[i-1][w], f[i][w])
            if weights[i] <= w:
                f[i][w] = max(f[i][w], f[i-1][w-weights[i]] + values[i])

    return f[-1][-1]

# weights = [10, 20, 30]
# values = [60, 100, 120]
print(knapsack(weights, values, s))

### FIXED CODE ###

n, s = [int(i) for i in  raw_input().split()]
weights = []
values = []

for _ in xrange(n):
    w, v = [int(i) for i in raw_input().split()]
    weights.append(w)
    values.append(v)

def knapsack(weights, values, limit):
    n = len(weights)
    # f = [[0 for _ in xrange(limit+1)] for _ in xrange(n)]

    prev = [0 for _ in xrange(limit+1)]

    if weights[0] <= limit:
        for w in xrange(weights[0], limit+1):
            prev[w] = values[0]

    for i in xrange(1, n):
        # print prev
        current = [0] * (limit+1)
        for w in xrange(1, limit+1):
            current[w] = max(prev[w], current[w])
            if weights[i] <= w:
                current[w] = max(current[w], prev[w-weights[i]] + values[i])
        prev = list(current)

    return prev[-1]

# weights = [10, 20, 30]
# values = [60, 100, 120]
print(knapsack(weights, values, s))
### BUGGY CODE ###

h,w = map(int,input().split())
a = [input() for _ in range(h)]
ans = 0
dic = {}
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            if not i in dic.keys():
                dic[i] = []
            dic[i].append(j)
ans = 0
for i in range(h):
    for j in range(w):
        if a[i][j]=='.':
            tmp = 10**4
            for key in dic.keys():
                for m in dic[key]:
                    tmp = min(tmp,abs(key-i)+abs(m-j))
            ans = max(ans,tmp)
print(ans)

### FIXED CODE ###

h,w = map(int,input().split())
a = [input() for _ in range(h)]
ans = 0
queue = []
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            queue.append([i,j])
from collections import deque
queue = deque(queue)
dxy = [(0,1), (0,-1), (1,0), (-1,0)]
dp = [[10**4]*w for _ in range(h)]
for i,j in queue:
    dp[i][j] = 0
while len(queue):
    y,x = queue.popleft()
    d = dp[y][x]
    for dx,dy in dxy:
        nx, ny = x+dx, y+dy
        if not 0<=nx<=w-1:
            continue
        elif not 0<=ny<=h-1:
            continue
        elif dp[ny][nx]<=d+1:
            continue
        dp[ny][nx] = d+1
        queue.append((ny,nx))
print(max([max(dp[row]) for row in range(h)]))
### BUGGY CODE ###

N, K = map(int, input().split())
P = list(map(lambda x: int(x)-1, input().split()))
C = list(map(int, input().split()))

visited = [False]*N
lp = [[0] for _ in range(N)]

lidx = 0
for s in range(N):
    if visited[s]:
        continue

    nex = s
    while not visited[nex]:
        visited[nex] = True
        now = P[nex]
        nex = now
        lp[lidx].append(lp[lidx][-1] + C[now])

    lidx += 1

ans = -(10**10)

for k in range(lidx):
    loop = lp[k]
    km = loop[-1]
    
    lenloop = len(loop)-1

    pt = 0

    kk = K

    x = max(kk//lenloop-1, 0)
    if km > 0:
        pt += x*km
    kk -= x*lenloop

    # print(x, kk, km)

    for i in range(lenloop*2):
        loop.append(loop[i+1]+km)
    
    for i in range(lenloop):
        for j in range(i+1, i+kk+1):
            # print(i, j, loop[j]-loop[i])
            ans = max(loop[j]-loop[i]+pt, ans)

# print(lp)

print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(lambda x: int(x)-1, input().split()))
C = list(map(int, input().split()))

visited = [False]*N
lp = [[0] for _ in range(N)]

lidx = 0
for s in range(N):
    if visited[s]:
        continue

    nex = s
    while not visited[nex]:
        visited[nex] = True
        now = P[nex]
        nex = now
        lp[lidx].append(lp[lidx][-1] + C[now])

    lidx += 1

ans = -(10**10)

for k in range(lidx):
    loop = lp[k]
    km = loop[-1]
    
    lenloop = len(loop)-1

    pt = 0

    kk = K

    x = max(kk//lenloop-1, 0)
    if km > 0:
        pt += x*km
    kk -= x*lenloop

    # print(x, kk, km)

    for i in range(lenloop*2):
        loop.append(loop[i+1]+km)
    
    for i in range(lenloop):
        for j in range(i+1, i+kk+1):
            # print(i, j, loop[j]-loop[i])
            ans = max(loop[j]-loop[i]+pt, ans)

# print(lp)

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

N=int(raw_input())

num=[]
for i in range(N):
    num.append(int(raw_input()))

sn=set(num)

c=0
for n in sn:
    if num.count(n)%2==1:
        c+=1

print c

### FIXED CODE ###

N=int(raw_input())

num={}
for i in range(N):
    a=int(raw_input())
    if a in num:
        num[a]^=1
    else:
        num[a]=1

c=0
for k in num:
    if num[k]==1:
        c+=1
print c
### BUGGY CODE ###

from collections import deque
n , q = map(int,input().split())
lot = [[] for i in range(n)]
ans = [[] for i in range(n)]
for i in range(n-1):
    a, b = map(int,input().split())
    lot[a-1].append(b-1)
    lot[b-1].append(a-1)
tyu = [0]*n
for i in range(q):
    p , x = map(int,input().split())
    tyu[p-1] += x

taiki = deque()
taiki.append(0)
owari = []
while  taiki:
    s = taiki.pop()
    for i in lot[s]:
        if owari.count(i) == 0:
            tyu[i] += tyu[s]
            taiki.append(i)
    owari.append(s)
for i in tyu:
    print(i,end=" ")


### FIXED CODE ###

from collections import deque
n , q = map(int,input().split())
lot = [[] for i in range(n)]
for i in range(n-1):
    a, b = map(int,input().split())
    lot[a-1].append(b-1)
    lot[b-1].append(a-1)
tyu = [0]*n
for i in range(q):
    p , x = map(int,input().split())
    tyu[p-1] += x

taiki = deque()
taiki.append(0)
owari = [True] * n
while  taiki:
    s = taiki.pop()
    for i in lot[s]:
        if owari[i]:
            tyu[i] += tyu[s]
            taiki.append(i)
    owari[s] = False
print(*tyu)
### BUGGY CODE ###

N = int(input())
sheet = [[0 for i in range(10)] for i in range(10)]
cnt = 0

for i in range(1, N + 1):
  str_i = str(i)
  if sheet[int(str_i[0])][int(str_i[-1])] == 0:
    for j in range(N + 1):
      str_j = str(j)
      if str_j[0] == str_i[-1] and str_j[-1] == str_i[0]:
        sheet[int(str_i[0])][int(str_i[-1])] += 1
    cnt += sheet[int(str_i[0])][int(str_i[-1])]

  else:
    cnt += sheet[int(str_i[0])][int(str_i[-1])]


print(cnt)

### FIXED CODE ###

N = int(input())
sheet = [[0 for i in range(10)] for i in range(10)]
cnt = 0

for i in range(1, N + 1):
  str_i = str(i)
  sheet[int(str_i[0])][int(str_i[-1])] += 1

res = 0
for i in range(10):
  for j in range(10):
    res += sheet[i][j] * sheet[j][i]

print(res)
### BUGGY CODE ###

import math
A,B = map(int, input().split())

y = max(A,B)
x = min(A,B)
while y%x != 0:
  tmp = x
  x = y%x
  y = tmp

p = [1]
for val in range(2,x+1):
  flag = 1
  if x % val == 0:
    for i in range(2,int(math.sqrt(val))+1):
      if val % i == 0:
        flag = 0
        break
    if flag == 1:
      p.append(val)
print(len(p))
  

### FIXED CODE ###

import math
A,B = map(int, input().split())

# 最大公約数の算出
y = max(A,B)
x = min(A,B)
while y%x != 0:
  tmp = x
  x = y%x
  y = tmp

# 素因数分解
p = []
tmp = int(math.sqrt(x))+1
for n in range(2,tmp):
  while x % n == 0:
    x /= n
    p.append(n)
p.append(int(x))
p.append(1)
p = list(set(p))
print(len(p))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
D = list(map(int,input().split()))
# from random import randint

# n = randint(1, 50)
# D = [randint(0, 12) for i in range(n)]

C = [0] * 13
C[0] = 1
for i in range(n):
    C[D[i]] += 1

if C[0] >= 2 or C[12] >=2:
    print(0)
    sys.exit()

for i in range(13):
    if C[i] >= 3:
        print(0)
        sys.exit()

D = []
for i in range(13):
    for j in range(C[i]):
        D.append(i)
n = len(D)
A = [0] * n
ans0 = 0
for i in range(2**n):
    ib = format(i, "b").zfill(n)
    for j in range(n):
        A[j] = D[j] * (-1) ** int(ib[j])
    ans = 30
    for j in range(n):
        for k in range(j+1, n):
            di = abs(A[k] - A[j])
            # print(ans)
            ans = min(ans, min(di, 24-di))
    # print(ib, ans0,ans)
    ans0 = max(ans0, ans)
print(ans0)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
D = list(map(int,input().split()))
# from random import randint

# n = randint(1, 50)
# D = [randint(0, 12) for i in range(n)]

C = [0] * 13
C[0] = 1
for i in range(n):
    C[D[i]] += 1

if C[0] >= 2 or C[12] >=2:
    print(0)
    sys.exit()

for i in range(13):
    if C[i] >= 3:
        print(0)
        sys.exit()

# D = []
# for i in range(13):
#     for j in range(C[i]):
#         D.append(i)
# n = len(D)
# A = [0] * n

# print(C)
ans0 = 0
for i in range(2**13):
    zero = 0
    ib = format(i, "b").zfill(13)
    A = []
    for j in range(13):
        if C[j] == 1:
            A.append(j * (-1) ** int(ib[j]))
        if C[j] == 2:
            if int(ib[j]) == 0:
                A.append(j)
                A.append(-j)
            else:
                zero = 1
    if zero == 1:
        continue
    # print("not cont")
    ans = 30
    # if len(A)>1:
        # print(A)
    # print(ib, A)
    for j in range(len(A)):
        for k in range(j+1, len(A)):
            di = abs(A[k] - A[j])
            # print(ans)
            ans = min(ans, min(di, 24-di))
            if ans <= ans0:
                break
        if ans <= ans0:
            break
    # print(ib, ans0,ans)
    ans0 = max(ans0, ans)
print(ans0)
### BUGGY CODE ###

n = int(input())
s = input()

count_min = 10**5

for i in range(n):
    s0 = s[:i].count('W')
    s1 = s[i+1:].count('E')
    count = s0+s1
    count_min = min(count_min, count)    
 
print(count_min)

### FIXED CODE ###

n = int(input())
s = input()

w, e = 0, 0
W = [0]*n
E = [0]*n
for i in range(n):
    if s[i] == 'W':
        w += 1
        W[i] += w 
        E[i] = e
    else:
        e += 1
        E[i] += e
        W[i] = w

count_min = E[-1]
for i in range(1, n):
    count = W[i-1] + (E[-1] - E[i]) 
    count_min = min(count_min, count)

print(count_min)
### BUGGY CODE ###

from collections import deque
from itertools import chain
H, W = map(int, input().split())
G = chain.from_iterable([[s == '#' for s in input()] for _ in range(H)])
dist = [0]*(H*W)
B = deque([i for i, g in enumerate(G) if g])
visited = set(B)
while B:
    vij = B.pop()
    for dij in (W, -W, 1, -1):
        nij = vij + dij
        if (dij == 1 and not nij % W) or (dij == -1 and not (nij+1) % W) or not (0 <= nij < H*W) or nij in visited:
            continue
        visited.add(nij)
        dist[nij] = 1 + dist[vij]
        B.appendleft(nij)
print(max(dist))

### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
G = [input() for _ in range(H)]
dist = [0]*(H*W)
bn = 0
B = deque()
geta = W
for i, g in enumerate(G):
    for j, f in enumerate(g):
        if f == '#':
            bn += 1
            B.append(i*geta + j)
visited = set(B)
while bn < H*W:
    if not B:
        break
    dh, dw = divmod(B.pop(), geta)
    dhw = dh * geta + dw
    for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        ni, nj = dh + di, dw + dj
        if not (0 <= ni <= H - 1) or not (0 <= nj <= W - 1):
            continue
        nij = ni * geta + nj
        if nij in visited or G[ni][nj] == '#':
            continue
        visited.add(nij)
        dist[nij] = 1 + dist[dhw]
        B.appendleft(nij)
print(max(dist))
### BUGGY CODE ###

from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
import random
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])
def graphm():
    n=inp()
    g=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b,w=inpm()
        a-=1
        b-=1
        g[a].append((b,w))
        g[b].append((a,w))
    return n,g
def dijkstra(s,to,n,g): # sからの最短距離 頂点数n
    s -= 1
    que = []
    d = [10**15 for _ in range(n)]
    d[s] = 0
    heappush( que,(0,s) )
    while len(que)>0:
        p =  heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(g[v])):
            edge = g[v][i]
            if d[edge[0]] > d[v] + edge[1]:
                d[edge[0]] = d[v] + edge[1]
                heappush( que,(d[edge[0]] , edge[0]) )
    return d[to-1]

def main():
    n,graph = graphm()
    q,k = inpm()
    for _ in range(q):
        x,y = inpm()
        print( dijkstra(x,k,n,graph) + dijkstra(k,y,n,graph) )    

if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import Counter,defaultdict,deque
import sys
import copy
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def main():
    n=int(input())
    graph = [[] for _ in range(n)]
    for _ in range(n-1):
        a,b,w=map(int,input().split())
        a-=1
        b-=1
        graph[a].append((b,w))
        graph[b].append((a,w))
    graph = tuple(graph)
    q,k = map(int,input().split())
    que = deque([k-1])
    dis = [-1 for _ in range(n)]
    dis[k-1]=0
    while que:
        i = que.pop()
        for j in range(len(graph[i])):
            go = graph[i][j][0]
            d = graph[i][j][1]
            if dis[go]==-1:
                dis[go] = dis[i] + d
                que.append(go)
    for _ in range(q):
        x,y = map(int,input().split())
        print( dis[x-1] + dis[y-1] ) 

if __name__ == "__main__":
    main()