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

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    A.sort()
    MOD = 10 ** 9 + 7
    ans = 1

    if K % 2 == 1 and A[-1] < 0:
        for i in range(K):
            ans *= A[N - (i + 1)]

        ans = ans % MOD
        print(ans)
        return

    l = 0
    r = N - 1
    if K % 2 == 1:
        ans = ans * A[r]
        r -= 1
    
    for _ in range(K // 2):
        ml = A[l] * A[l + 1]
        mr = A[r] * A[r - 1]
        if ml > mr:
            ans = ans * ml % MOD
            l += 2
        else:
            ans = ans * mr % MOD
            r -= 2

    print(ans)
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    A.sort()
    MOD = 10 ** 9 + 7
    ans = 1

    if K % 2 == 1 and A[-1] < 0:
        for i in range(K):
            ans = ans * A[N - (i + 1)] % MOD

        print(ans)
        return

    l = 0
    r = N - 1
    if K % 2 == 1:
        ans = ans * A[r]
        r -= 1
    
    for _ in range(K // 2):
        ml = A[l] * A[l + 1]
        mr = A[r] * A[r - 1]
        if ml > mr:
            ans = ans * ml % MOD
            l += 2
        else:
            ans = ans * mr % MOD
            r -= 2

    print(ans)
    return


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

from heapq import heappush,heappop
import queue
import re
import math
import functools


def int_raw():
    return int(input())

def ss_raw():
    return input().split()

def ints_raw():
    return list(map(int, ss_raw()))

INF = 1<<29

def make1d_arr(n,val=INF):
    return [val for i in range(n)]

def make2d_arr(h,w,val =INF):
    return [[val for i in range(w)]for i in range(h)]

def gcd (a,b):
    if(b==0):
        return a
    return gcd(b,a%b)

H,W = ints_raw()
AS = []
for _ in range(H):
    AS.append(input())

DFST = make2d_arr(H,W,-1)



def main():
    qu = queue.Queue()
    dirs = [[1,0,1],[0,1,1],[-1,0,1],[0,-1,1]]
    ans = 0
    for h in range(H):
        for w in range(W):
            if AS[h][w]=="#":
                DFST[h][w]=0
                qu.put([h,w,0])
    while not qu.empty():
        cpos = qu.get()
        for dir in dirs:
            npos = [cpos[0]+dir[0],cpos[1]+dir[1],cpos[2]+dir[2]]
            if npos[0]<0 or npos[0]>=H or npos[1]<0 or npos[1]>=W:
                continue
            if DFST[npos[0]][npos[1]]!=-1:
                continue
            DFST[npos[0]][npos[1]]=npos[2]
            ans = max(ans,npos[2])
            qu.put(npos)
    return ans

print(main())


### FIXED CODE ###

from collections import deque

def ss_raw():
    return input().split()

def ints_raw():
    return list(map(int, ss_raw()))

INF = 1<<29

def main():
    H,W = ints_raw()
    DFST = [[-1 for i in range(W)]for i in range(H)]
    qu = deque()
    dirs = [[1,0,1],[0,1,1],[-1,0,1],[0,-1,1]]
    ans = 0
    for h in range(H):
        S = input()
        for w in range(W):
            if S[w]=="#":
                DFST[h][w]=0
                qu.append([h,w,0])
    while len(qu)!=0:
        cpos = qu.popleft()
        for dir in dirs:
            
            ny,nx,nt = [cpos[0]+dir[0],cpos[1]+dir[1],cpos[2]+dir[2]]
            if ny<0 or ny>=H or nx<0 or nx>=W:
                continue
            if DFST[ny][nx]!=-1:
                continue
            DFST[ny][nx]=nt
            ans = max(ans,nt)
            qu.append([ny,nx,nt])
    return ans

print(main())
### BUGGY CODE ###

from collections import defaultdict as dd
from sys import exit
n = int(input())
A = list(map(int, input().split()))

coutner = 0
dp = dd(int)
dp[1] = 1
for depth in range(n):
    mov_dic = dd(lambda: 0)
    for now_num, total in dp.items():
        if now_num - A[depth] > 0:
            mov_dic[now_num - A[depth]] = total
    #print("mov_dic", mov_dic)

    dp = dd(int)
    for now_num, total in mov_dic.items():
        for next_num in range(now_num, now_num*2 + 1):
            dp[next_num] = max(total + next_num, dp[next_num])
    #print("dp", dp)

if dp[A[-1]] == 0:
    print(-1)
else:
    print(dp[A[-1]])

### FIXED CODE ###

from collections import defaultdict as dd
import bisect
from sys import exit
n = int(input())
A = list(map(int, input().split()))

coutner = 0
dp = dd(int)
dp[1] = 1
limit = [0] * (n + 1)
total = 0
for i in range(n, -1, -1):
    total += A[i]
    limit[i] = total
#print(limit)

"""
for depth in range(n):
    mov_dic = dd(lambda: 0)
    for now_num, total in dp.items():
        if now_num - A[depth] > 0:
            mov_dic[now_num - A[depth]] = total
    #print("mov_dic", mov_dic)

    dp = dd(int)
    mov_dic_keys = set(mov_dic.keys())
    for now_num, total in mov_dic.items():
        mov_dic_keys.remove(now_num)
        for next_num in range(now_num, min(now_num*2 + 1, limit[depth] + 1)):
            if now_num in mov_dic_keys:
                break
            dp[next_num] = max(total + next_num, dp[next_num])
    #print(limit[depth], "dp", dp)

if dp[A[-1]] == 0:
    print(-1)
else:
    print(dp[A[-1]])
"""

if n == 0:
    if A[0] == 1:
        print(1)
    else:
        print(-1)
    exit()

now_num = 1
now_total = 1
for depth in range(n):
    mov_num = now_num - A[depth]
    #print(mov_num)

    if mov_num > 0:
        now_num = min(mov_num * 2, limit[depth+1])
        now_total += now_num
    else:
        print(-1)
        exit()
if now_num == A[n]:
    print(now_total)
else:
    print(-1)
### BUGGY CODE ###

def main():
    input()
    t = input()
    dic = {'R': [], 'G': [], 'B': []}
    for i in range(len(t)):
        dic[t[i]].append(i)
    count = 0
    for i in dic['R']:
        for j in dic['G']:
            for k in dic['B']:
                ids = sorted([i, j, k])
                if ids[1] - ids[0] != ids[2] - ids[1]:
                    count += 1
    print(count)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main3():
    n = int(input())
    s = input()

    ans = s.count("R") * s.count("B") * s.count("G")
    for i in range(n):
        for j in range(i, n):
            k = 2 * j - i
            if k >= n: break
            if s[i] != s[j] and s[j] != s[k] and s[i] != s[k]:
                ans -= 1

    print(ans)

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

#ABC055.B
N = int(input())
cnt = 1

for i in range(N):
    cnt = cnt*(i+1)

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

### FIXED CODE ###

#ABC055.B
import math
N = int(input())
ans = math.factorial(N)%(10**9+7)
print(ans)
### BUGGY CODE ###

n,k = map(int,input().split())
a = [int(i) for i in input().split()]
d = [0]*(n+1)
for x in range(k):
    for i in range(n):
        l = max(0,i-a[i])
        r = min(n-1,i+a[i])+1
        d[l] += 1
        d[r] -= 1
    for i in range(n): d[i+1] += d[i]
    if x == k-1: break
    for i in range(n):
        if d[i] != n: break
    else:
        break
    a = d[:]
    d = [0]*(n+1)
print(*d[:n])

### FIXED CODE ###

n,k = map(int,input().split())
a = [int(i) for i in input().split()]
d = [0]*(n+1)
for x in range(k):
    for i in range(n):
        l = max(0,i-a[i])
        r = min(n-1,i+a[i])+1
        d[l] += 1
        d[r] -= 1
    for i in range(n): d[i+1] += d[i]
    if x == k-1: break
    for i in range(n):
        if d[i] != n: break
    else:
        break
    a = d[:]
    d = [0]*(n+1)
print(*d[:n])
### BUGGY CODE ###

n=int(input())
a=[int(x) for x in input().split()]
a.sort()
max=a[-1]
dp=[False for _ in range(max+1)]

for i in a:
    if dp[i]==False:
        j=1
        while 1:
            j+=1
            if i*j>max:
                break
            dp[i*j]=True
for i in a:
    if a.count(i)>1:
        dp[i]=True
cnt=0
for i in a:
    if dp[i]==False:
        cnt+=1

print(cnt)



### FIXED CODE ###

n=int(input())
a=[int(x) for x in input().split()]
a.sort()
max=a[-1]
dp=[False for _ in range(max+1)]

for i in a:
    if dp[i]==False:
        j=1
        while 1:
            j+=1
            if i*j>max:
                break
            dp[i*j]=True
for i in range(len(a)-1):
    if a[i]==a[i+1]:
        dp[a[i]]=True
cnt=0
for i in a:
    if dp[i]==False:
        cnt+=1

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

#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import defaultdict


def solve():
  N = int(input())
  S = str(input())

  dct = defaultdict(lambda:set([]))
  for i in range(N):
    for j in range(i+1,N+1):
      dct[S[i:j]].add(i)

  for sn in sorted(dct.keys(),key=lambda x:-len(x)):
    if len(dct[sn]) < 2:
      continue
    else:
      if max(dct[sn])-min(dct[sn]) >= len(sn):
        return len(sn)
  return 0

print(solve())

### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-



N = int(input())
S = str(input())

r,i,j = 0,0,0
while j < N:
  t = S[i:j]
  if t in S[j:]:
    r = max(r,j-i)
    j += 1
  else:
    i += 1
print(r)
### BUGGY CODE ###

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=998244353
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,k=LI()
  field=[LI() for _ in range(k)]
  field.sort()

  rng=[]
  for x,y in field:
    for z in range(x,y+1):
      rng.append(z)

  # print(rng)

  dp=[0]*(n+1)
  dp[1]=1

  for i in range(1,n):
    for dx in rng:
      if i+dx>n:
        break
      dp[i+dx]+=dp[i]
      dp[i+dx]%=mod
    # print(dp)
  
  return dp[n]%mod

# main()
print(main())


### FIXED CODE ###

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=998244353
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,k=LI()
  field=[LI() for _ in range(k)]

  dp=[0]*(n+1)
  dpsum=[0]*(n+1)
  dp[1]=1
  dpsum[1]=1

  for i in range(2,n+1):
    for l,r in field:
      li=i-r
      ri=i-l
      if ri<=0:
        continue
      li=max(1,li)
      dp[i]+=dpsum[ri]-dpsum[li-1]
      dp[i]%=mod
    dpsum[i]=dp[i]+dpsum[i-1]
    dpsum[i]%=mod
  
  return dp[n]%mod

# main()
print(main())
### BUGGY CODE ###

N = int(input())
S = input()

ans = [0] * 3
count = 0
for i in range(0, 1000):
    if (i < 10):
        s = '00' + str(i)
    elif (i >= 10 and i < 100):
        s = '0' + str(i)
    else:
        s = str(i)
    idx = 0
    for i in range(N):
        if (S[i] == s[idx]):
            ans[idx] = i + 1
            idx += 1
        if (0 not in ans):
            count += 1
            ans = [0] * 3
            break
print(count)


### FIXED CODE ###

N = int(input())
S = input()

count = 0
for p in range(10):
    s = S.find(str(p))
    if s == -1:
        continue
    for q in range(10):
        t = S.find(str(q), s + 1)
        if t == -1:
            continue
        for r in range(10):
            u = S.find(str(r), t + 1)
            if u != -1:
                count += 1
print(count)
### BUGGY CODE ###

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

for i in range(M):
  if A[N-1] == 0:
    break
  A[N-1] >>= 1
  A = sorted(A)
  
print(sum(A))

### FIXED CODE ###

import heapq
N, M = map(int, input().split())
A = map(int, input().split())
AA = [-1 * x for x in A]
#print(AA)
heapq.heapify(AA)

for i in range(M):
  a = heapq.heappop(AA)
  #print(a, -a>>1)
  heapq.heappush(AA, -(-a >> 1))

print(-sum(AA))
### BUGGY CODE ###

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

b = []

for i in range(n):
    b.append(a[i])
    b.reverse()

b = list(map(str, b))
print(' '.join(b))

### FIXED CODE ###

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

a_even = a[0::2]
a_odd  = a[1::2] 

# even
if (n - 1) % 2 == 0: # 0-(n-1)の実施なので(n-1)の偶奇を判定
    b = a_even.copy()
    b.reverse()
    b = b + a_odd
# odd
else:
    b = a_odd.copy()
    b.reverse()
    b = b + a_even

b = list(map(str, b))
print(' '.join(b))
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
maxp = 0
for i in range(n + 1 - k):
    e_temp = 0
    for j in range(k):
        e_temp += p[i + j]
    if e_temp > maxp:
        maxp = e_temp
a = (maxp + k) / 2
print(a)

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
temp = 0
dif = 0
if k < n:
    for i in range(n - k):
        next_dif = p[i + k] - p[i]
        dif += next_dif
        if dif > 0:
            temp = i + 1
            dif = 0
s = 0
for i in range(temp, temp + k):
    s += p[i]
a = (s + k) / 2
print(a)
### BUGGY CODE ###

from bisect import bisect

N = int(input())
A = sorted(map(int, input().split()))
B = sorted(map(int, input().split()))
C = sorted(map(int, input().split()))

D = tuple(N - bisect(C, b) for b in B)
print(sum(sum(D[bisect(B, a):]) for a in A))


### FIXED CODE ###

from bisect import bisect
from itertools import accumulate

n = int(input())
a_list = sorted(map(int, input().split()))
b_list = sorted(map(int, input().split()))
c_list = sorted(map(int, input().split()))

b_c_table_ = list(accumulate(reversed(tuple(n - bisect(c_list, b) for b in b_list))))
b_c_table_.reverse()
b_c_table_ += [0]

print(sum(b_c_table_[bisect(b_list, a)] for a in a_list))
### BUGGY CODE ###

n, k = map(int, input().split())
L = list(map(int, input().split()))
d = {}
for a in L:
    if a not in d:
        d[a] = 1
    else:
        d[a] += 1
l = []
for v in d.values():
    l.append(v)

if len(l) <= k:
    print(0)
else:
    ans = float('inf')
    for i in range(2 ** len(l)):
        b = [0] * len(l)
        for j in range(len(l)):
            if ((i >> j) & 1):
                b[j] = 1
        cnt = 0
        val = len(l)
        for m in range(len(l)):
            if l[m] * b[m] == 0:
                cnt += l[m]
                val -= 1
        if val <= k:
            ans = min(ans, cnt)
    print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
L = list(map(int, input().split()))
d = {}
for a in L:
    if a not in d:
        d[a] = 1
    else:
        d[a] += 1
l = []
for v in d.values():
    l.append(v)
l.sort(reverse=True)
print(n - sum(l[:k]))
### BUGGY CODE ###

N = int(input())
input_line = [input() for _ in range(N)]
count = {}
for w in input_line:
    if w in count:
        count[w] += 1
    else:
        count[w] = 1

keys = [k for k, v in count.items() if v == max(count.values())]
for w in sorted(keys):
    print(w)


### FIXED CODE ###

N = int(input())
input_line = [input() for _ in range(N)]
count = {}
for w in input_line:
    if w in count:
        count[w] += 1
    else:
        count[w] = 1
max_values = max(count.values())
keys = [k for k, v in count.items() if v == max_values]
for w in sorted(keys):
    print(w)
### BUGGY CODE ###

k = int(input())
a = list(map(int,input().split()))

#始めの人数がn人だった時終わりの人数
def g(n,a,k):
    for i in range(k):
        n = n - (n%a[i])
    return n

#print(g(8,a,k))

s = 0
t = 2 + k*max(a)
for i in range(100):
    m = (s+t)//2
    if g(m,a,k)> 2:
        t = m
    else:
        s = m
    
p = 0
q = 2+k*max(a)
for i in range(100):
    m = (p+q)//2
    if g(m,a,k) >= 2:
        q = m
    else:
        p = m

c = 1
if g(s,a,k) == 2:
    res = s
elif g(t,a,k) == 2:
    res = t
else:
    c = -1

if g(q,a,k) == 2:
    res2 = q
elif g(p,a,k) == 2:
    res2 = p
else:
    c = -1

if c == 1:
    print(res2,res)
else:
    print(-1)

### FIXED CODE ###

k = int(input())
a = list(map(int,input().split()))
a = a[::-1]

c = 2 #min
d = 2 #max
res = 1 #判定

for i in range(k):
    if d < a[i]:
        res = -1
        break
    if i != k-1:
        if c % a[i] != 0 or d % a[i] != 0:
            res = -1
            break
        else:
            d = d + a[i] -1
            p = c%a[i+1]
            q = d%a[i+1]
            if p == 0:
                c2 = c
            else:
                c2 = c + a[i+1]-p
            d2 = d-q
            
            if c2 <= d2:
                c = c2
                d = d2
            else:
                res = -1
                break
    else:
        d = d + a[i] -1
            
        
    
    
if res == -1:
    print(-1)
else:
    print(str(c) + ' ' + str(d))
### BUGGY CODE ###

K, S = map(int, input().split())
K = K + 1
count = 0
for i in range(K):
    for j in range(K):
        for k in range(K):
            if i + j + k > S:
                continue
            if i + j + k == S:
                count += 1
print(count)


### FIXED CODE ###

K, S = map(int, input().split())
count = 0
for x in range(K + 1):
    for y in range(K + 1):
        z = S - x - y
        if 0 <= z <= K:
            count = count + 1

print(count)
### BUGGY CODE ###

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

count = [2]*x
ans = []

for i in range(2**x):
    for j in range(x):
        if ((i>>j)&1):
            count[j]=4
    ans.append(sum(count))

if ans.count(y):
    print('Yes')
else:
    print('No')

### FIXED CODE ###

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

for i in range(x+1):
    foot = 2*i + 4* (x-i)
    if foot == y:
        print('Yes')
        exit()
print('No')
### BUGGY CODE ###

import sys

alp = [[] for _ in range(26)]

s = input()
t = input()
#s = 'contest'
#t = 'programming'

for i, x in enumerate(s):
    alp[ord(x) - 97].append(i)

ind_prev = -1
loop = 0
flag = True
for x in t:
    letter = alp[ord(x) - 97]

    if len(letter) == 0:
        print(-1)
        flag = False
        break
        
    if ind_prev >= letter[-1]:
        ind_prev = -1
        loop += 1

    for y in letter:
        if y > ind_prev:
            ind_prev = y
            break

if flag:
    print(loop * len(s) + ind_prev + 1)



### FIXED CODE ###

import numpy as np
from bisect import bisect_right

alp = [[] for _ in range(26)]

s = input()
t = input()
#s = 'contest'
#t = 'programming'

for i, x in enumerate(s):
    alp[ord(x) - 97].append(i)

ind_prev = -1
loop = 0
flag = True
for x in t:
    letter = alp[ord(x) - 97]

    if len(letter) == 0:
        print(-1)
        flag = False
        break
        
    if ind_prev >= letter[-1]:
        ind_prev = -1
        ind_prev_each_letter = [0 for _ in range(26)]
        loop += 1

    ind = bisect_right(letter, ind_prev)
    ind_prev = letter[ind]

if flag:
    print(loop * len(s) + ind_prev + 1)
### BUGGY CODE ###

N, M = [ int(i) for i in input().strip().split(' ') ]
H    = [ int(i) for i in input().strip().split(' ') ]
paths = [ input().strip().split(' ') for _m in range(M)]
paths = [ [int(p1), int(p2)] for p1, p2 in paths ]
count = 0
for n in range(1, N+1):
    is_good = True
    for path in paths:
        if n not in list(path):
            continue
        if (path[0] == n) and (H[n-1] <= H[path[1]-1]):
            is_good = False
            break
        if (path[1] == n) and (H[n-1] <= H[path[0]-1]):
            is_good = False
            break
    
    if is_good:
        count += 1
print(count)

### FIXED CODE ###

N, M = [ int(i) for i in input().strip().split(' ') ]
H    = [ int(i) for i in input().strip().split(' ') ]
paths = []
max_neighbor = [ 0 for _ in range(N)]

for _m in range(M):
    path = input().strip().split(' ')
    path = int(path[0]), int(path[1])
    max_neighbor[path[0]-1] = max(max_neighbor[path[0]-1], H[path[1]-1])
    max_neighbor[path[1]-1] = max(max_neighbor[path[1]-1], H[path[0]-1])
count = 0
for n in range(N):
    if max_neighbor[n] < H[n]:
        count += 1
print(count)
### BUGGY CODE ###

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

c = [0] * n

for i in range(n):
    for j in range(i):
        #print(p[i],p[j])
        if p[i] > p[j]:
            c[i] = 1

print(c.count(0))

### FIXED CODE ###

n = int(input())
p = [int(i) for i in input().split()]
x = p[0]
ans = 0
for i in p:
    if x >= i:
        ans += 1
        x = i
print(ans)
### BUGGY CODE ###

from itertools import combinations_with_replacement
def f(n):
    ret = 0
    for x, y, z in combinations_with_replacement(range(1, 100), 3):
        if x**2+y**2+z**2+x*y+y*z+z*x==n:
            if x==y==z:
                ret += 1
            elif x==y or y==z or z==x:
                ret += 3
            else:
                ret += 6
    return ret
N = int(input())
for n in range(1, N+1):
    print(f(n))

### FIXED CODE ###

from itertools import combinations_with_replacement
def f(N):
    global table
    for x, y, z in combinations_with_replacement(range(1, 100), 3):
        n = x**2+y**2+z**2+x*y+y*z+z*x
        if n>N:
            continue
        if x==y==z:
            table[n] += 1
        elif x==y or y==z or z==x:
            table[n] += 3
        else:
            table[n] += 6
N = int(input())
table = [0 for _ in range(N+1)]
f(N)
for n in range(1, N+1):
    print(table[n])
### BUGGY CODE ###

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

import heapq

def dijkstra_heap(s):
    d = [float('inf')] * N
    used = [False] * N
    d[s] = 0
    used[s] = True
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist, e)
    while len(edgelist):
        min_edge = heapq.heappop(edgelist)
        if used[min_edge[1]]:
            continue
        v = min_edge[1]
        d[v] = min_edge[0]
        used[v] = True
        for e in edge[v]:
            heapq.heappush(edgelist, [e[0] + d[v], e[1]])
    return d

for q in query:
    x, y = q[0], q[1]
    x -= 1
    y -= 1
    dist = dijkstra_heap(K-1)
    print(dist[x] + dist[y])

### FIXED CODE ###

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

import heapq

def dijkstra_heap(s):
    d = [10**12] * N
    used = [False] * N
    d[s] = 0
    used[s] = True
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist, e)
    while len(edgelist):
        min_edge = heapq.heappop(edgelist)
        if used[min_edge[1]]:
            continue
        v = min_edge[1]
        d[v] = min_edge[0]
        used[v] = True
        for e in edge[v]:
            heapq.heappush(edgelist, (e[0] + d[v], e[1]))
    return d

dist = dijkstra_heap(K-1)
for q in query:
    x, y = q[0], q[1]
    x -= 1
    y -= 1
    print(dist[x] + dist[y])
### BUGGY CODE ###

x=input()
while "SSTT" in x:x=x.replace("SSTT","")
while "ST" in x:x=x.replace("ST","")
print(len(x))

### FIXED CODE ###

l=[]
for i in input():
    if i=="S":l.append("S")
    elif len(l)==0 or l[-1]=="T":l.append("T")
    else:l.pop()
print(len(l))