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

from collections import defaultdict
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def root(par, x):
    if par[x] == x:
        return x
    else:
        return root(par, par[x])


def same(par, x, y):
    return root(par, x) == root(par, y)


def unite(rank, par, x, y):
    x = root(par, x)
    y = root(par, y)

    if x == y:
        return

    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1


def main():
    N, K, L = map(int, readline().split())
    m = map(int, read().split())
    pq = list(zip(m, m))
    pq, rs = pq[:K], pq[K:]

    d_c = defaultdict(list)
    d_t = defaultdict(list)

    par = list(range(N))
    rank = [0] * N
    for p, q in pq:
        p -= 1
        q -= 1
        unite(rank, par, p, q)

    for i in range(N):
        par[i] = root(par, i)

    par_t = list(range(N))
    rank_t = [0] * N
    for r, s in rs:
        r -= 1
        s -= 1
        unite(rank_t, par_t, r, s)

    for i in range(N):
        par_t[i] = root(par_t, i)

    for i in range(N):
        d_c[par[i]].append(i)
        d_t[par_t[i]].append(i)

    for i in range(N):
        d_c[i] = d_c[par[i]]
        d_t[i] = d_t[par_t[i]]

    cnt = [0] * N
    for i in range(N):
        cnt[i] = len(list(set(d_c[i]) & set(d_t[i])))

    print(*cnt)


main()


### FIXED CODE ###

from collections import defaultdict
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def root(par, x):
    if par[x] == x:
        return x
    else:
        return root(par, par[x])


def unite(rank, par, x, y):
    x = root(par, x)
    y = root(par, y)

    if x == y:
        return

    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1


def main():
    N, K, L = map(int, readline().split())
    m = map(int, read().split())
    pq = list(zip(m, m))
    pq, rs = pq[:K], pq[K:]

    par = list(range(N))
    rank = [0] * N
    for p, q in pq:
        p -= 1
        q -= 1
        unite(rank, par, p, q)

    par_t = list(range(N))
    rank_t = [0] * N
    for r, s in rs:
        r -= 1
        s -= 1
        unite(rank_t, par_t, r, s)

    pp = [(0, 0)]*N
    dd = defaultdict(list)
    for i in range(N):
        par[i] = root(par, i)
        par_t[i] = root(par_t, i)
        pp[i] = (par[i], par_t[i])
        dd[pp[i]].append(i)

    cnt = [0] * N
    for i in range(N):
        cnt[i] = len(dd[pp[i]])

    print(*cnt)


main()
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
 
b=list(set(a))
c=0
for i in range(len(b)):
    er = a.count( b[i] ) - b[i]
    if er<0:
        c+= a.count( b[i] )
    else:
        c+=er
print(c)

### FIXED CODE ###

from collections import Counter

n=int(input())
a=list(map(int,input().split()))
counter=Counter(a)
b=list(set(a))
c=0
for i in b:
    k =  counter[i]
    c+= k-i if k-i>=0 else k
print(c)
### BUGGY CODE ###

import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# Ciの値でsortする、Tを0000で固定した後、最後に2**N倍
N = ir()
C = np.array(lr())
MOD = 10 ** 9 + 7
C.sort()
two_power = np.array([(1+N-i) * 2**(N-2) % MOD if i < N-1 else 2 ** i % MOD for i in range(N)])
answer = (C * two_power % MOD).sum() * 2**N
print(answer%MOD)


### FIXED CODE ###

import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# Ciの値でsortする、Tを0000で固定した後、最後に2**N倍
N = ir()
C = np.array(lr())
MOD = 10 ** 9 + 7
C.sort()
two_power = np.array([(1+N-i) * pow(2, (N-2), MOD) % MOD if i < N-1 else pow(2, i, MOD) for i in range(N)])
answer = (C * two_power % MOD).sum() * 2**N
print(answer%MOD)
### BUGGY CODE ###

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
from collections import Counter

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

fr,to,w=[],[],[]

for i in range(n-1):
  fr.append(i)
  to.append(i+1)
  w.append(1)

fr.append(x-1)
to.append(y-1)
w.append(1)

g=csr_matrix((w, (fr, to)), shape=(n, n))

ans_l=[]
for i in range(n):
  d=dijkstra(g,indices=i,directed=False)
  for i in d:
    if 1<=i<=10**5:
      ans_l.append(i)


c=Counter(ans_l)
for i in sorted(c.keys()):
  print(c[i]//2)
for i in range(n-1-len(c.keys())):
  print(0)

### FIXED CODE ###

from collections import Counter

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

x-=1
y-=1

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

c=Counter(dist)
for i in range(1,n):
  print(c[i])
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
ans = list()
for i in range(1, N + 1):
    ans.append(str(a.index(i) + 1))
print(' '.join(ans))

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
ans = [-1] * N
for i in range(N):
    ai = a[i]
    ans[ai - 1] = str(i + 1)
print(' '.join(ans))
### BUGGY CODE ###

s = input()
t = input()
ans = ''
slen = len(s)
tlen = len(t)

dp = [[0 for i in range(tlen+1)] for j in range(slen+1)]

for i in range(slen):
    for j in range(tlen):
        if s[i]==t[j]:
            dp[i+1][j+1]=max(dp[i][j]+1,dp[i+1][j],dp[i][j+1])
        else:
            dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])
#ここまでで、DP配列が完成
#あとはDPの最後から遡る
i = slen
j = tlen
while (i>0 and j>0):
    if dp[i][j]==dp[i-1][j]:
        i -= 1
        continue
    elif dp[i][j]==dp[i][j-1]:
        j -= 1
        continue
    else:
        #print(i,j)
        ans = s[i-1] + ans
        i -= 1
        j -= 1
        
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
s = input()
t = input()
ans = ''
slen = len(s)
tlen = len(t)

dp = [[0 for i in range(tlen+1)] for j in range(slen+1)]

for i in range(slen):
    for j in range(tlen):
        if s[i]==t[j]:
            dp[i+1][j+1]=max(dp[i][j]+1,dp[i+1][j],dp[i][j+1])
        else:
            dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])
#ここまでで、DP配列が完成
#あとはDPの最後から遡る
i = slen
j = tlen
while (i>0 and j>0):
    if dp[i][j]==dp[i-1][j]:
        i -= 1
        continue
    elif dp[i][j]==dp[i][j-1]:
        j -= 1
        continue
    else:
        #print(i,j)
        ans = s[i-1] + ans
        i -= 1
        j -= 1
        
print(ans)
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
q = int(input())
M = list(map(int, input().split()))


def solve(i, m):
    if m == 0:
        return True
    elif i >= n:
        return False
    elif m - A[i] >= 0:
        res = solve(i + 1, m) or solve(i + 1, m - A[i])
        return res
    else:
        res = solve(i + 1, m)
        return res

for m in M:
    if solve(0, m):
        print('yes')
    else:
        print('no')

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
q = int(input())
M = list(map(int, input().split()))

table = [[-1 for i in range(max(M)+1)] for j in range(n)]

def solve(i, m):
    if m == 0:
        return True
    elif i >= n:
        return False
    elif table[i][m] != -1:
        return table[i][m]
    elif m - A[i] >= 0:
        res = solve(i + 1, m) or solve(i + 1, m - A[i])
        table[i][m] = res
        return res
    else:
        res = solve(i + 1, m)
        table[i][m] = res
        return res

for m in M:
    if solve(0, m):
        print('yes')
    else:
        print('no')
### BUGGY CODE ###

n = int(input())
 
result = 0
for i in range(1, n + 1):
    for j in range(1, (n // i) + 1):
        result += i * j
print(result)

### FIXED CODE ###

n = int(input())

result = 0
for i in range(1, n + 1):
    for j in range(1, (n // i) + 1):
        result += i * j
print(result)
### BUGGY CODE ###

from networkx import*
g=Graph()
for a,b in[*map(str.split,open(x:=0))][1:]:g.add_edge(a,'y'+b)
for c in connected_components(g):a,b=map(len,bipartite.sets(s:=g.subgraph(c)));x+=a*b-len(s.edges)
print(x)

### FIXED CODE ###

class UnionFind():
    def __init__(self,size):
        self.table=[-1]*size
    def root(self,x):
        while self.table[x]>=0:
            x=self.table[x]
        return x
    def unite(self,x,y):
        s1=self.root(x)
        s2=self.root(y)
        if s1!=s2:
            if self.table[s1]>self.table[s2]:
                s1,s2=s2,s1
            self.table[s1]+=self.table[s2]
            self.table[s2]=s1
        return
    def same(self,x,y):
        return self.root(x)==self.root(y)
    def size(self,x):
        return -self.table[self.root(x)]
n,*z=map(int,open(0).read().split())
u=UnionFind(10**5*2+1)
for x,y in zip(*[iter(z)]*2):
    u.unite(x,10**5+y)
d=[[0,set(),set()]for _ in range(10**5*2+1)]
for x,y in zip(*[iter(z)]*2):
    t=d[u.root(x)]
    t[0]+=1
    t[1].add(x)
    t[2].add(y)
print(sum(len(x)*len(y)-a for a,x,y in d))
### BUGGY CODE ###

from collections import Counter
import numpy as np

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

tar = [1] * (1 + 10 ** 5)
tar = np.array(tar)

for i in range(m):
    l, r = map(int, input().split())
    tar[:l-1] = 0
    tar[r:] = 0

tar = tar.tolist()
#print(tar[0:5])
count = Counter(tar)
ans = count[1]
print(ans)


### FIXED CODE ###

from collections import Counter
import numpy as np

n, m = map(int, input().split())
data = [0] * m

for i in range(m):
    data[i] = list(map(int, input().split()))


data = np.array(data)
ll = data[:, 0]
rr = data[:, 1]

ans = np.min(rr) - max(ll) + 1
ans = max(0, ans)
print(ans)

'''
n, m = map(int, input().split())
tar = [0] * (1 + 10 ** 5)
tar = np.array(tar)

for i in range(m):
    l, r = map(int, input().split())
    tar[l:r + 1] += 1
    #print(tar[:10])

#tar = tar.tolist()
# print(tar[0:5])
count = Counter(tar)
ans = count[m]
print(ans)
#-----------------------------
n, m = map(int, input().split())

ll, rr = map(int, input().split())
for i in range(m - 1):
    l, r = map(int, input().split())

    #lについて
    if (l <= ll):
      pass
    elif (ll < l )

ans = max(ll - rr, 0)
print(ans)

'''
### BUGGY CODE ###

def cwrlp(data,r):
	if r <= 0:
		return []
	
	result = []
	_cwrlp(data, r, 0, [], result)
	return result

def _cwrlp(data, r, start, progress, result):
	if r == 0:
		result.append(progress)
		return
	
	for i in range(start, len(data)):
		_cwrlp(data, r-1, i, progress + [data[i]], result)

n,m,q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(q)]

dataset = cwrlp(range(1,m+1),n)

#print(dataset)
ret = 0
for da in dataset:
#	print(da)
	ans = 0
	for i in range(q):
		a = abcd[i][0]
		b = abcd[i][1]
		c = abcd[i][2]
		d = abcd[i][3]
		if(da[b-1]-da[a-1] == c):
			ans += d
#			print(a,b,c,d,ans)
	ret = max(ret,ans)
print(ret)

### FIXED CODE ###

def cwrlp(data,r):
	if r <= 0:
		return []
	
	result = []
	_cwrlp(data, r, 0, [], result)
	return result

def _cwrlp(data, r, start, progress, result):
	if r == 0:
		result.append(progress)
		return
	
	for i in range(start, len(data)):
		_cwrlp(data, r-1, i, progress + [data[i]], result)

n,m,q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(q)]

#dataset = cwrlp(range(1,m+1),n)

#print(dataset)
ret = 0
for da in cwrlp(range(1,m+1),n):
#	print(da)
	ans = 0
	for i in range(q):
		a = abcd[i][0]
		b = abcd[i][1]
		c = abcd[i][2]
		if(da[b-1]-da[a-1] == c):
			d = abcd[i][3]
			ans += d
#			print(a,b,c,d,ans)
	ret = max(ret,ans)
print(ret)
### BUGGY CODE ###

import sys
def main():
  input = sys.stdin.readline
  maxa=0
  N=int(input())
  L=list(map(int,input().split()))
  L=sorted(L)
  R=tuple(set(L))
  for i in range(len(R)):
    s=L.count(R[i])+L.count(R[i]+1)+L.count(R[i]-1)
    maxa=max(maxa,s)
  print(maxa)
if __name__ == '__main__':
    main()

### FIXED CODE ###

maxa=0
N=int(input())
L=list(map(int,input().split()))
c=[0]*100000
for i in L:
  c[i]+=1
for i in range(1,99999):
  s=c[i]+c[i-1]+c[i+1]
  maxa=max(maxa,s)
print(maxa)
### BUGGY CODE ###

from sys import stdin
N, M = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) for x in stdin.readline().rstrip().split()]
BC = [[int(x) for x in stdin.readline().rstrip().split()] for _ in range(M)]
BC.sort(key=lambda x: x[1], reverse=True)
for i in range(M):
    A = A + [BC[i][1]] * BC[i][0]
    if len(A) >= 2 * N:
        break

A.sort(reverse=True)
print(sum(A[:N]))


### FIXED CODE ###

from sys import stdin
N, M = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) for x in stdin.readline().rstrip().split()]
BC = [[int(x) for x in stdin.readline().rstrip().split()] for _ in range(M)]
BC.sort(key=lambda x: x[1], reverse=True)
for i in range(M):
    A.extend([BC[i][1]] * BC[i][0])
    if len(A) >= 2 * N:
        break

A.sort(reverse=True)
print(sum(A[:N]))
### BUGGY CODE ###

n = int(input())
a_lst = [int(elem) for elem in input().split()]

lst = []
for i in range(n):
    lst.append(i - a_lst[i])

lst2 = []
for j in range(n):
    lst2.append(j + a_lst[j])

cnt = 0
for i in range(n-1):
    for j in range(i+1, n):
        if lst2[i] == lst[j]:
            cnt += 1
print(cnt)



### FIXED CODE ###

n = int(input())
a_lst = [int(elem) for elem in input().split()]

dic = {}
for i in range(n):
    if not i - a_lst[i] in dic:
        dic[i - a_lst[i]] = 1
    else:
        dic[i - a_lst[i]] += 1
        
cnt = 0
for j in range(n):
    if j + a_lst[j] in dic:
        cnt += dic[j + a_lst[j]]

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

N, M = map(int, input().split())
A = sorted([int(i) for i in input().split()])

BC = [[int(i) for i in input().split()] for _ in range(M)]
BC = sorted(BC, key=lambda x: x[1])[::-1]

i = 0
for B, C in BC :
    if i + B <= N :
        A += [C] * B
    else :
        A += [C] * (N - i)
        break

print(sum(sorted(A)[-1:-N-1:-1]))

### FIXED CODE ###

N, M = map(int, input().split())
A = [[1, int(i)] for i in input().split()]
BC = A + [[int(i) for i in input().split()] for _ in range(M)]

BC.sort(key=lambda x: x[1], reverse=True)

i = 0
res = 0

for B, C in BC :
    if i + B <= N :
        res += C * B
        i += B
    else :
        res += C * (N - i)
        break

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

N=int(input())
lis = list(map(int, input().split()))
ans=1
for a in lis:
    ans*=a
if ans > pow(10,18):
    print(-1)
else:
    print(ans)

### FIXED CODE ###

N=int(input())
lis = list(map(int, input().split()))
ans=1
j=True
if lis.count(0) > 0:
    print(0)
else:
    for a in lis:
        ans*=a
        if ans > pow(10,18):
            j=False
            break
    if j:
        print(ans)
    else:
        print(-1)
### BUGGY CODE ###

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

while True:
  if k <= n:
    n -= k
  elif n > k//2:
    n = k - n
  else:
    break

    
print(n)
    

### FIXED CODE ###

[n, k] = map(int, input().split())
 
n -= (n//k) * k
if n > k//2:
  n = k -n
print(n)
### BUGGY CODE ###

vs = set()
def dfs_w(d, stack):
    depth = [-1] + [0]*N
    pvs = set()
    if stack[0] in vs:
        return True
    while stack:
        v, dpd = stack.pop()
        vs.add(v)
        pvs.add(v)

        for u, dpd in d[v]:
            if u in pvs:
                if depth[u] != depth[v] + dpd:
                    return False
            if u in vs:
                continue
            depth[u] = depth[v] + dpd
            stack += [(u, dpd)]

    return True

if __name__ == '__main__':
    N, M = map(int, input().split())
    G = [set() for _ in range(N+1)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        G[a].add((b,c))
        G[b].add((a,-c))
    for i in range(N):
        if i in vs:
            continue
        stack = [(i+1, 0)] 
        r =  dfs_w(G, stack)
        if not r:
            break
    if r:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

import sys
input = sys.stdin.readline
vs = set()
def dfs_w(d, stack):
    depth = defaultdict(int)
    pvs = set()
    while stack:
        v = stack.pop()
        vs.add(v)
        pvs.add(v)
        for u, dpd in d[v]:
            if u in pvs:
                if depth[u] != depth[v] + dpd:
                    return False
            if u in vs:
                continue
            depth[u] = depth[v] + dpd
            stack.append(u)
    return True

if __name__ == '__main__':
    from collections import defaultdict
    N, M = map(int, input().split())
    G = defaultdict(set)
    for _ in range(M):
        a, b, c = map(int, input().split())
        G[a].add((b,c))
        G[b].add((a,-c))
    for i in range(N):
        if i+1 in vs:
            continue
        stack = [i+1] 
        r =  dfs_w(G, stack)
        if not r:
            break
    if r:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import bisect
n,k=map(int,input().split())
a=list(map(int,input().split()))
N=[];Z=[];P=[]
for i in range(n):
  if a[i]<0:
    N.append(a[i])
  elif a[i]==0:
    Z.append(a[i])
  else:
    P.append(a[i])

if k<=len(N)*len(P):
  for i in range(len(N)):
    N[i]*=-1
  N.sort()
  P.sort()
  L=0;R=10**18+1
  while R-L>1:
    x=(L+R)//2
    ct=0
    for j in range(len(N)):
      ct+=len(P)-bisect.bisect_left(P,(x+N[j]-1)//N[j])
    if ct<k:
      R=x
    else:
      L=x
  print(-L)

elif k<=len(N)*len(P)+(len(Z)*(len(Z)-1))//2+len(Z)*(len(N)+len(P)):
  print(0)

else:
  y=len(N)*len(P)+(len(Z)*(len(Z)-1))//2+len(Z)*(len(N)+len(P))
  for i in range(len(N)):
    N[i]*=-1
  N.sort()
  P.sort()
  L=0;R=10**18+1
  while R-L>1:
    x=(L+R)//2
    ct=0
    for j in range(1,len(N)):
      ct+=bisect.bisect_right(N[0:j],x//N[j])
    for j in range(1,len(P)):
      ct+=bisect.bisect_right(P[0:j],x//P[j])
    if ct<k-y:
      L=x
    else:
      R=x
  print(R)

### FIXED CODE ###

import bisect
n,k=map(int,input().split())
a=list(map(int,input().split()))
N=[];Z=[];P=[]
for i in range(n):
  if a[i]<0:
    N.append(a[i])
  elif a[i]==0:
    Z.append(a[i])
  else:
    P.append(a[i])

if k<=len(N)*len(P):
  for i in range(len(N)):
    N[i]*=-1
  N.sort()
  P.sort()
  Nr=list(reversed(N))
  L=0;R=10**18+1
  while R-L>1:
    x=(L+R)//2
    ct=0
    ct2=0
    for j in range(len(Nr)):
      if ct2!=len(P):
        while Nr[j]*P[ct2]<x:
          ct2+=1
          if ct2==len(P):
            break
      ct+=len(P)-ct2
    if ct<k:
      R=x
    else:
      L=x
  print(-L)

elif k<=len(N)*len(P)+(len(Z)*(len(Z)-1))//2+len(Z)*(len(N)+len(P)):
  print(0)

else:
  y=len(N)*len(P)+(len(Z)*(len(Z)-1))//2+len(Z)*(len(N)+len(P))
  for i in range(len(N)):
    N[i]*=-1
  N.sort()
  P.sort()
  L=0;R=10**18+1
  Nr=list(reversed(N))
  Pr=list(reversed(P))
  while R-L>1:
    x=(L+R)//2
    ct=0
    ct2=0
    for j in range(len(Nr)):
      if ct2!=len(N):
        while Nr[j]*N[ct2]<=x:
          ct2+=1
          if ct2==len(N):
            break
      ct+=min(ct2,len(N)-1-j)
    ct3=0
    for j in range(len(Pr)):
      if ct3!=len(P):
        while Pr[j]*P[ct3]<=x:
          ct3+=1
          if ct3==len(P):
            break
      ct+=min(ct3,len(P)-1-j)
    if ct<k-y:
      L=x
    else:
      R=x
  print(R)
### BUGGY CODE ###

n = int(input())
li = list(map(int,input().split()))
a = 1
if 0 in li:
    print(0)
else:
    for i in li:
         a *= i
    if a >= 10**18+1:
        print('-1')
    else:
        print(a)


### FIXED CODE ###

n = int(input())
li = list(map(int,input().split()))
a = 1
if 0 in li:
    print(0)
else:
    li = sorted(li, reverse=True)
    for i in li:
        if a >= 10**18+1:
            break
        else:
            a *= i
    if a >= 10**18 + 1:
        print('-1')
    else:
        print(a)
### BUGGY CODE ###

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

a =[]
for i in range(n):
    a.append(ab[i][0])

b = []
for i in range(n):
    b.append(ab[i][1])

x = 0 #本数
y = 0 #金額

while m > x:
    if b[a.index(min(a))] > 0:
        y += min(a)
        b[a.index(min(a))] -= 1
        x += 1
    else:
        del b[a.index(min(a))]
        del a[a.index(min(a))]
        continue

print(y)


### FIXED CODE ###

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

ab.sort(key=lambda x:x[0])

cnt = 0
price = 0
i = 0
while cnt < m:
    price += ab[i][0] * ab[i][1]
    cnt += ab[i][1]
    if cnt > m:
        price -= ab[i][0] * (cnt - m)
        break
    i += 1

print(price)
### BUGGY CODE ###

mod = 10 ** 9 + 7
S = input()
abc = 0
bc = 0
c = 0
q = 0

for i in range(len(S)-1, -1, -1):
    if S[i] == 'C':
        c = 3 ** q + c
    if S[i] == 'B':
        bc += c
    if S[i] == 'A':
        abc += bc
    if S[i] == '?':
        abc = abc * 3 + bc
        bc = bc * 3 + c
        c = c * 3 + 3 ** q
        q += 1
        
print(abc % mod)

### FIXED CODE ###

S = input()
mod = 10 ** 9 + 7
abc = 0
bc = 0
c = 0
q = 0

for i in S[::-1]:
    if i == 'A':
        abc = (bc + abc) % mod
    if i == 'B':
        bc = (c + bc) % mod
    if i == 'C':
        c = (pow(3, q, mod) + c ) % mod
    if i == '?':
        abc = (abc * 3 + bc) % mod
        bc = (bc * 3 + c) % mod
        c = (pow(3, q, mod) + c * 3) % mod
        q += 1
        
print(int(abc))
### BUGGY 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 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]:
            if p[1]==to-1:
                break
            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 dijkstra1(s,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
 
def main():
    n,graph = graphm()
    q,k = inpm()
    pre2 = dijkstra1(k,n,graph)
    pre1=[]
    for i in range(n):
        pre1.append(dijkstra(i+1,k,n,graph))
    for _ in range(q):
        x,y = inpm()
        print( pre1[x-1] + pre2[y-1] ) 

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()