Harryxun/stf_run huggingface dataset:
h,n=map(int,input().split())
ab = [list(map(int,input().split())) for i in range(n)]

dp=[float('inf')]*(h+1)
dp[0]=0
for i in range(h):
    for j in range(n):
		temp_a = i + ab[j][0] if i + ab[j][0] <= h else h
        temp_b = dp[i] + ab[j][1]
        dp[temp_a]=min(dp[temp_a],temp_b)
print(dp[-1])


### FIXED CODE ###

h,n=map(int,input().split())
a,b=[],[]
for i in range(n):
    A,B=map(int,input().split())
    a.append(A)#ダメージ量
    b.append(B)#消費魔力

dp=[float('inf')]*(h+1)
dp[0]=0
for i in range(h):
    for j in range(n):

        next=i+a[j] if i+a[j]<=h else h
        dp[next]=min(dp[next],dp[i]+b[j])
print(dp[-1])
import math

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


def lcm(x, y):
    return (x * y) // math.gcd(x, y)


num1 = math.floor(B / C) - math.floor((A - 1) / C)
num2 = math.floor(B / D) - math.floor((A - 1) / D)
num3 = math.floor(B / lcm(C, D)) - math.floor((A - 1) / lcm(C, D))


print(B - A + 1 - (num1 + num2 - num3))

### FIXED CODE ###

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


def gcd(x, y):
    while x % y > 0:
        x, y = y, x % y
    return y


def lcm(x, y):
    return (x * y) // gcd(x, y)


num1 = B // C - (A - 1) // C
num2 = B // D - (A - 1) // D
num3 = B // lcm(C, D) - (A - 1) // lcm(C, D)


print(B - A + 1 - (num1 + num2 - num3))
X, Y = map(int, input().split())
MOD = 10**9+7

N = min(X,Y)
def pow_mod(x, n):
    if n == 0:
        return 1
    elif n % 2 == 0:
        return pow_mod(x * x % MOD, n // 2) % MOD
    else:
        return x * pow_mod(x * x % MOD, n // 2) % MOD

fact = [1]
for i in range(1,N+1):
    fact.append( (fact[i-1] * i) % MOD )

inv = [1] * (N+1)
inv[N] = pow_mod(fact[N], MOD-2)
for i in range(N, 1, -1):
    inv[i-1] = inv[i] * (i) % MOD

def cmb_mod(n,r):
    return fact[n] * inv[r] * inv[n-r] % MOD


cnt = 0
x,y = X,Y
while x > 0 and y > 0:
    if x == 2*y or y == 2*x:
        break
    x -= 3
    y -= 3
    cnt += 1

ans = 0
if x == 0 and y == 0:
    ans = cmb_mod(cnt*2, cnt)
elif x == 2*y or y == 2*x:
    ans = cmb_mod(cnt+2, cnt) * (cnt+1) % MOD

print(ans)


### FIXED CODE ###

X, Y = map(int, input().split())
MOD = 10**9+7

N = 10**6+1
def pow_mod(x, n):
    if n == 0:
        return 1
    elif n % 2 == 0:
        return pow_mod(x * x % MOD, n // 2) % MOD
    else:
        return x * pow_mod(x * x % MOD, n // 2) % MOD

fact = [1]
for i in range(1,N+1):
    fact.append( (fact[i-1] * i) % MOD )

inv = [1] * (N+1)
inv[N] = pow_mod(fact[N], MOD-2)
for i in range(N, 1, -1):
    inv[i-1] = inv[i] * (i) % MOD

def cmb_mod(n,r):
    return fact[n] * inv[r] * inv[n-r] % MOD


if (X+Y) % 3 != 0:
    print(0)
else:
    n = (2*X - Y) // 3
    m = (2*Y - X) // 3
    if n < 0 or m < 0:
        print(0)
    else:
        print(cmb_mod(n+m, n))
n = input()

INFTY = 10000000

color = [0 for i in xrange(n)]
M = [[0 for i in xrange(n)] for i in xrange(n)]
d = [INFTY for i in xrange(n)]
p = [-1 for i in xrange(n)]

def MST():
  d[0] = 0
  p[0] = -1

  while True:
    cost = INFTY
    for i in xrange(n):
      if color[i] != 1 and d[i] < cost:
        cost = d[i]
        u = i

    if cost == INFTY:
      break
    color[u] = 2

    for v in xrange(n):
      if color[v] != 2 and M[u][v] != INFTY:
      if M[u][v] < d[v]:
        d[v] = M[u][v]
        p[v] = u
        color[v] = 1:

  sum = 0
  for i in xrange(n):
    if p[i] != -1:
      sum += M[i][p[i]] 
  return sum

for i in xrange(n):
  G = map(int, raw_input().split())
  for j in range(n):
   if G[j] == -1:
     M[i][j] = INFTY
   else:
     M[i][j] = G[n]

print MST()

### FIXED CODE ###

n = input()

INFTY = 10000000

color = [0 for i in xrange(n)]
M = [[INFTY for i in xrange(n)] for i in xrange(n)]
d = [INFTY for i in xrange(n)]
p = [-1 for i in xrange(n)]

def MST():
  d[0] = 0

  while True:
    cost = INFTY
    for i in xrange(n):
      if color[i] != 2 and d[i] < cost:
        cost = d[i]
        u = i

    if cost == INFTY:
      break
    
    color[u] = 2

    for v in xrange(n):
      if color[v] != 2 and M[u][v] != INFTY and M[u][v] < d[v]:
        d[v] = M[u][v]
        p[v] = u
        color[v] = 1

  sum = 0
  for i in xrange(n):
    if p[i] != -1:
      sum += M[i][p[i]]
  return sum

for i in xrange(n):
  G = map(int, raw_input().split())
  for j in range(n):
   if G[j] != -1:
     M[i][j] = G[j]

print MST()
# coding: utf-8
# Your code here!
def saiki(num,lis):
    if num==6:
        temp=0
        for i in range(6):
            temp+=lis[i]*10**(5-i)
        if (temp+amari)%13==5:
            cand.append(lis)
        return 0
    else:
        for i in range(10):
            saiki(num+1,lis+[i])
            

S=list(input())
N=len(S)

num=[0]*6#左から大きい
que=[0]*6

for i in range(N):
    if S[i]=="?":
        que[i%6]+=1
    else:
        num[i%6]+=int(S[i])

for i in range(6):
    num[i]%=10
amari=0
for i in range(6):
    amari+=(num[i]*10**(5-i))%13
amari%=13

cand=[]
saiki(0,[])

#print(amari)
#print(cand)
"""
ans=0
for item in cand:
    temp=1
    for i in range(6):
        if que[i]==0 and item[i]!=0:
            temp=0
            break
        else:
            for j in range(que[i]-1):
                temp*=(item[i]+que[i]-j-1)
    ans+=temp
    """
    """
    if temp!=0:
        print(item)
        print(ans)
    """
    """
print(ans%(10**9+7))
            
"""

### FIXED CODE ###

S=list(input())
N=len(S)

dp=[[0 for i in range(13)] for j in range(N+1)]
dp[0][0]=1

for i in range(N):
    if S[i]=="?":
        temp=10**((N-i-1)%6)
        for j in range(10):
            for k in range(13):
                dp[i+1][(k+j*temp)%13]+=dp[i][k]
                dp[i+1][(k+j*temp)%13]%=10**9+7
                    
    else:
        temp=int(S[i])*10**((N-i-1)%6)
        for k in range(13):
            dp[i+1][(k+temp)%13]+=dp[i][k]
            dp[i+1][(k+temp)%13]%=10**9+7

print(dp[-1][5])
import sys
input = sys.stdin.readline


def main():
    N, P = map(int, input().split())
    if N == 1:
        print(P)
        return
    x = ans = 1
    while True:
        y = x**N
        if y > P:
            break
        if P % y == 0:
            ans = x
        x += 1
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


def main():
    N, P = map(int, input().split())
    p = prime_factorize(P)
    import collections
    ans = 1
    for k, v in collections.Counter(p).most_common():
        while v >= N:
            ans *= k
            v -= N
    print(ans)


if __name__ == '__main__':
    main()
n=int(input())
x=[int(input()) for i in range(11)]
print(1000*x-n)

### FIXED CODE ###

n=int(input())
a=n%1000
if a==0:
    print(0)
else:
    print(1000-a)
for e in iter(input,'0'):
 e=int(e)
 print(sum(e//5**ifor i in range(1,6)))


### FIXED CODE ###

for e in iter(input,'0'):print(sum(int(e)//5**i for i in range(1,7)))
from corections import Counter 
n = int(input())
v = list(map(int,input().split()))
 
odd = []
even = []
for i in range(n//2):
	odd.append(v[2*i+1])
	even.append(v[2*i])
 
odd = sorted(odd)
even = sorted(even)
ac = Counter(odd).most_common(2)
bc = Counter(even).most_common(2)
def cnt(X):
	count = 0
	ans = 0
	for i in range(len(X)-1):
		if X[i+1] == X[i]:
			count += 1
			ans = max(ans,count)
		else:
			count = 0
	return ans+1
            
if ac[0][0] != bc[0][0]:
  print(len(v)-cnt(odd)-cnt(even))
elif len(ac) == 1 and len(bc) == 1:
	print(n//2)
else:
	print(n-max(ac[0][1]+bc[1][1],ac[1][1]+bc[0][1]))

### FIXED CODE ###

from collections import Counter 
n = int(input())
v = list(map(int,input().split()))
 
odd = []
even = []
for i in range(n//2):
	odd.append(v[2*i+1])
	even.append(v[2*i])

odd = sorted(odd)
even = sorted(even)
ac = Counter(odd).most_common(2)
bc = Counter(even).most_common(2)
def cnt(X):
	count = 0
	ans = 0
	for i in range(len(X)-1):
		if X[i+1] == X[i]:
			count += 1
			ans = max(ans,count)
		else:
			count = 0
	return ans+1
            
if ac[0][0] != bc[0][0]:
  print(len(v)-cnt(odd)-cnt(even))
elif len(ac) == 1 and len(bc) == 1:
	print(n//2)
else:
	print(n-max(ac[0][1]+bc[1][1],ac[1][1]+bc[0][1]))
# import itertools
# import pprint
import copy
from collections import deque

gem,ope = map(int,input().split())
vlist = deque(map(int,input().split()))

ans = 0

for l in range(ope+1):
  for r in range(ope-l+1):
    if l+r>ope:
      break

    x   = ope-l-r
    now = []
    deq = copy.copy(vlist) 

    for i in range(l):
      now.append(deq.popleft())
    for j in range(r):
      now.append(deq.pop())
    for k in range(x):
      if now==[]:
        break
      if min(now)<0:
        now.remove(min(now))
    
    if ans<sum(now):
      ans = sum(now)

print(ans)


### FIXED CODE ###

# import itertools
# import pprint
import copy
from collections import deque

gem,ope = map(int,input().split())
vlist = deque(map(int,input().split()))

ans = 0

for l in range(ope+1):
  for r in range(ope-l+1):
    if l+r>ope or l+r>gem:
      break

    x   = ope-l-r
    now = []
    deq = copy.copy(vlist) 

    for i in range(l):
      now.append(deq.popleft())
    for j in range(r):
      now.append(deq.pop())
    for k in range(x):
      if now==[]:
        break
      if min(now)<0:
        now.remove(min(now))
    
    if ans<sum(now):
      ans = sum(now)

print(ans)
import sys
while True :
    ab = sys.stdin.readline().split()
    a = ab[0].strip
    b = ab[1].strip
    if a == 0 and b == 0 :
        break
    else :
        #sorted(ab)
        #print(ab[0],ab[1])
        pass

### FIXED CODE ###

import sys
while True :
    ab = list(map(int,sys.stdin.readline().split()))
    a = ab[0]
    b = ab[1]
    if a == 0 and b == 0 :
        break
    else :
        ab = sorted(ab)
        print(ab[0],ab[1])
def solve():
    n, data = [x for x in input().split(" ")]
    n = int(n)
    if data[:n//2] == data[n//2:]:
        return "Yes"
    return "No"

if __name__ == "__main__":
    # test = int(input())
    # for _ in test:
    print(solve())

### FIXED CODE ###

n = int(input())
s = input()
if (s[0:n//2]==s[n//2:]):
  print("Yes")
else:
  print("No")
def ans():
  N = int(input())
  A = list(map(int,input().split()))

  def gcd(m, n):
    while n:
      m, n = n, m%n
    return m

  res = []
  k = max(A)
  f = False
  ind = A.index(k)
  if k%2 == 0:
    f = True
  for i in range(N):
    if i != ind:
      if f:
        if (k%A[i])%2 == 0:
          res.append(gcd(k, A[i]))
      else:
        if (k%A[i])%2 == 1:
          res.append(gcd(k, A[i]))
  print(max(res))
ans()

### FIXED CODE ###

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

def gcd(m, n):
  while n:
    m, n = n, m%n
  return m

L = [0]
R = [0]
for i in range(N):
  L.append(gcd(L[i], A[i]))
  R.append(gcd(R[i], A[-(i+1)]))
R = R[::-1]
ans = 0
for i in range(N):
  ans = max(ans, gcd(L[i], R[i+1]))
print(ans)
N = int(input())
A = list(map(int, input().split()))

def gcd(x, y):
    if x == 0 or y == 0:
        return max(x, y)
    if y == 0:
        return x
    return gcd(y, x % y)

from functools import lru_cache
@lru_cache(maxsize = None)

def L(x):
    if x <= 0:
        return 0
    else:
        return gcd(L(x-1), A[x-1])

def R(x):
    if x >= N - 1:
        return 0
    else:
        return gcd(A[x+1], R(x+1))

w = 1
for i in range(N):
    w = max(w, gcd(L(i), R(i)))

print(w)


### FIXED CODE ###

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

def gcd(x, y):
    if x == 0 or y == 0:
        return max(x, y)
    g = x % y
    if g == 0:
        return y
    return gcd(y, g)

R = [0] * N
R[N-1] = w = 0
for i in range(N-2, -1, -1):
    R[i] = w = gcd(w, A[i+1])

L = [0] * N
L[0] = w = 0
for i in range(1, N):
    L[i] = w = gcd(w, A[i-1])

w = 1
for i in range(N):
    w = max(w, gcd(L[i], R[i]))

print(w)
N = int(input())
A = list(map(int,input().split()))
saidaiA =[]
oya = 1/2
flag = True
for i in range(len(A)):
    ko = oya *2
    oya = ko - A[i]
    saidaiA.append(int(ko))
    # print("i=",i)
    # print("ko =",ko)
    # print("oya =",oya)
    if oya < 0:
        flag = False
ans = 0
# print(saidaiA)
motikosi = 0
for i in range(len(A)):
    if A[-i] + motikosi >= saidaiA[-i]:
        ans += saidaiA[-i]
        motikosi = saidaiA[-i]
    else:
        ans += A[-i] + motikosi
        motikosi = A[-i] + motikosi
if flag == True:
    print(int(ans)+1)
else:
    print(-1)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
if N == 0:
    if A[0] == 1:
        print(1)
    else:
        print(-1)
else:
    saidaiA =[]
    oya = 1
    flag = True
    for i in range(len(A)):
        if oya >= 5*10**13:
            ko = 10**14
        else:
            ko = oya *2
        if i == 0:
            ko = 1
        oya = ko - A[i]
        saidaiA.append(ko)
        if oya < 0:
            flag = False
    ans = 0
    # print(saidaiA)
    motikosi = 0
    for i in range(len(A)):
        if A[-i] + motikosi >= saidaiA[-i]:
            ans += saidaiA[-i]
            motikosi = saidaiA[-i]
        else:
            ans += A[-i] + motikosi
            motikosi = A[-i] + motikosi
    if flag == True:
        print(ans+1)
    else:
        print(-1)
n, m = map(int, input().split())

class UnionfindWithWeight():
    def __init__(self, n):
        self.dist    = [0]  * (n+1)
        self.ranks   = [0]  * (n+1)
        self.parents = [-1] * (n+1)
    def find_root(self, x):
        if self.parents[x] < 0:
            return self.dist[x], x
        else:
            tmp = self.find_root(self.parents[x])
            self.dist[x]    += tmp[0]
            self.parents[x] =  tmp[1]
            return self.dist[x], self.parents[x]
    def union(self, x, y, dist):
        x_root = self.find_root(x)[1]
        y_root = self.find_root(y)[1]
        diff = dist + self.dist[x] - self.dist[y]
        if x_root == y_root and diff != 0:
            # print("This dist is invalid.", flush=True)
            return -1
        if self.ranks[y_root] > self.ranks[x_root]:
            x_root ,y_root = y_root, x_root
            diff =- diff
        self.parents[y_root] = x_root
        self.dist[y_root] = diff
        if self.ranks[y_root] == self.ranks[x_root]:
            self.ranks[x_root] += 1

v=UnionfindWithWeight(n)
for i in range(m):
    l, r, d = list(map(int, input().split()))
    if v.union(l,r,d) == -1:
        print('No')
        import sys
        sys.exit()

print('Yes')


### FIXED CODE ###

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

# it watches only end of union
# for i in range(m):
#     l,r,d = map(int, input().split())
#     if ml[l] == -1 and ml[r] == -1:
#         ml[l] = 0
#         ml[r] = d
#     elif ml[l] != -1 and ml[r] == -1:
#         ml[r] = d + ml[l]
#         if ml[r] > n:
#             print('R', i, ml[l], ml[r], flush=True)
#             print('No', flush=True)
#             sys.exit()
#     elif ml[l] == -1 and ml[r] != -1:
#         ml[l] = ml[r] - d
#         if ml[l] < 1:
#             print('L', i, ml[l], ml[r], flush=True)
#             print('No', flush=True)
#             sys.exit()
#     else:
#         if ml[r] - ml[l] != d:
#             print('B', i, l, ml[l], r, ml[r], d, flush=True)
#             print('No', flush=True)
#             sys.exit()
# print('Yes', flush=True)

class UnionfindWithWeight():
    def __init__(self,n):
        self.parents=[-1]*n
        self.ranks=[0]*n
        self.dist=[0]*n
    def find(self,x):
        if self.parents[x]<0:
            return self.dist[x],x
        else:
            tmp=self.find(self.parents[x])
            self.dist[x]+=tmp[0]
            self.parents[x]=tmp[1]
            return self.dist[x],self.parents[x]
    def union(self,x,y,d):
        rx=self.find(x)[-1]
        ry=self.find(y)[-1]
        diff=d+self.dist[x]-self.dist[y]
        if rx==ry:
            if diff!=0:
                return True
            return False
        if self.ranks[ry]>self.ranks[rx]:
            rx,ry=ry,rx
            diff=-diff
        self.parents[ry]=rx
        self.dist[ry]=diff
        if self.ranks[ry]==self.ranks[rx]:
            self.ranks[rx]+=1
        return False
lrd = []
for i in range(m):
    l,r,d = list(map(int, input().split()))
    lrd.append([l,r,d])
v=UnionfindWithWeight(n)
for i in lrd:
    l, r, d = i
    if v.union(l-1,r-1,d):
        print('No')
        import sys
        sys.exit()
print('Yes')
n,m = map(int, input().split())
a = list(map(int, input().split()))

from functools import reduce
import fractions
import math
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)
def lcm(numbers):
    return reduce(lcm_base, numbers, 1)

num = lcm(a)
thr = m - num//2

if thr <= 0:
    print(0)
else:
    print(-(-thr//num))

### FIXED CODE ###

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

from functools import reduce
import fractions
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)
def lcm(numbers):
    return reduce(lcm_base, numbers, 1)

def get2(num):
    cnt=0
    while num %2==0:
        cnt+=1
        num//=2
    return cnt

div2=get2(a[0])
for i in range(len(a)):
    if div2 != get2(a[i]):
        print(0)
        exit()

num = lcm(a)
thr = m - num//2

if thr < 0:
    print(0)
else:
    print(thr//num + 1)
a, b, q = map(int, input().split())
sno = []
tno = []
dis = []
 
for i in range(a):
  sno.append(int(input()))
sno.append(10000)
 
for i in range(b):
  tno.append(int(input()))
tno.append(10000)
 
for i in range(q):
  dis.append(int(input()))
 
for i in range(q):
  sl = 0
  sr = 0
  tl = 0
  tr = 0
  
  for j in range(a):
    if sno[j] <= dis[i]:
      sl = dis[i] - sno[j]
      sr = sno[j+1] - dis[i]
      break
    else:
      pass
                
  for k in range(b):
    if tno[k] <= dis[i]:
      tl = dis[i] - tno[k]
      tr = tno[k+1] - dis[i]
      break
    else:
      pass
  
  lds = max(sl, tl)
  rds = max(sr, tr)
  dis = min(lds, rds)
  print(dis)

### FIXED CODE ###

date = input()
tdate=[]
 
for s in date:
  tdate.append(s)
  
if tdate[5] != "0":
  mon = int(tdate[5] + tdate[6])
else:
  mon = int(tdate[6])


if mon <= 4:
  print("Heisei")
else:
  print("TBD")
a,b,c=map(int,input().split())
if a < b < c:
 print(Yes)


### FIXED CODE ###

a,b,c=map(int,input().split())
if a < b < c:
 print("Yes")
else:
 print("No")
def read_line():
    return input().rstrip()

def read_ints():
    return [int(x) for x in read_line().split()]

def read_int():
    return int(read_line())

a, b = read_int()

c = a + b
if c >= 10:
    print('error')
else:
    print(c)

### FIXED CODE ###

def read_line():
    return input().rstrip()

def read_ints():
    return [int(x) for x in read_line().split()]

def read_int():
    return int(read_line())


a, b = read_ints()

c = a + b
if c >= 10:
    print('error')
else:
    print(c)
import fractions
import math

tmp = list(map(int,(input().split())))
a = tmp[0]
b = tmp[1]

#limit = round(min(fractions.gcd(a, b), max(math.sqrt(a), math.sqrt(b))))
limit = max(math.sqrt(a), math.sqrt(b))
cnt = 0
for i in range(2, limit+1):
  flag = False
  while (a % i == 0) and (b % i == 0):
    a = a // i
    b = b // i
    flag = True
  if flag:
    cnt += 1
   
print (cnt+1)

### FIXED CODE ###

import fractions
import math
from collections import deque

def prime(x):
  px = []
  limit = int(math.sqrt(x))
  for i in range(2, limit+1):
    flag = False
    while x % i == 0:
      flag = True
      x = x // i
    if flag:
      px.append(i)
  if x != 1:
    px.append(x)
  return px

tmp = list(map(int,(input().split())))
a = tmp[0]
b = tmp[1]

pa = prime(a)
pb = prime(b)

cnt = 1
j = 0

for i in range(len(pa)):
  while j < len(pb) and pb[j] < pa[i]:
    j += 1
  if j == len(pb):
    break
  elif pb[j] == pa[i]:
    cnt += 1
  
print (cnt)
def findSumOfDigits(n):
    sum_digits = 0
    while n > 0 :
        sum_digits += n % 10
        n //= 10
    return sum_digits

N = int(input())
range_A = range(2,100001)
min_total = 1000
for a in range_A:
	b = N - a
    if b < 1:continue
	sum_a = findSumOfDigits(a)
	sum_b = findSumOfDigits(b)
	total = sum_a + sum_b
	if total < min_total:
	min_total = total
print(min_total)

### FIXED CODE ###



#　各桁の和を計算する
def findSumOfDigits(n):
    sum_digits = 0
    while n > 0 :
        sum_digits += n % 10
        n //= 10
    return sum_digits


def main()->None:
    N = int(input())
    # AとBの各桁の和を求める。
    range_A = range(1,N+1)
    min_total = 100000
    for a in range_A:
        b = N - a
        if b < 1 : continue
        sum_a = findSumOfDigits(a)
        sum_b = findSumOfDigits(b)
        total = sum_a + sum_b
        if total < min_total:
            min_total = total
    print(min_total)


if __name__ == "__main__":
    main()
def dfs(l,d,k):
  for i in l[k]:
    if d[i[0]]==-1:
      d[i[0]]=d[k]+i[1]
      dfs(l,d,i[0])

n=int(input())
l=[[] for i in range(n)]
for i in range(n-1):
  a,b,c=map(int,input().split())
  l[a-1].append([b-1,c])
  l[b-1].append([a-1,c])
q,k=map(int,input().split())
d=[-1 for i in range(n)]
d[k-1]=0
dfs(l,d,k-1)
L=[list(map(int,input().split())) for i in range(q)]
for i in range(q):
  print(d[L[i][0]-1]+d[L[i][1]-1])

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

def dfs(l,d,k):
  for i in l[k]:
    if d[i[0]]==-1:
      d[i[0]]=d[k]+i[1]
      dfs(l,d,i[0])

n=int(input())
l=[[] for i in range(n)]
for i in range(n-1):
  a,b,c=map(int,input().split())
  l[a-1].append([b-1,c])
  l[b-1].append([a-1,c])
q,k=map(int,input().split())
d=[-1 for i in range(n)]
d[k-1]=0
dfs(l,d,k-1)
L=[list(map(int,input().split())) for i in range(q)]
for i in range(q):
  print(d[L[i][0]-1]+d[L[i][1]-1])
if A <= 10 and B <= 10 :
    print(A*B)
else :
    print(-1)

### FIXED CODE ###

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

if A < 10 and B < 10 :
    print(A*B)
else :
    print(-1)
line = input()

if line[len(line)] == ("s"):
  line += "es"
else:
  line += "s"
print(line)

### FIXED CODE ###

line = input()
if line[len(line)-1] == "s":
	print(line + "es")
else:
  print(line + "s")