Harryxun/stf_run huggingface dataset:
N, K, *A = map(int, open(0).read().split())
MOD = 10 ** 9 + 7

z_num = sum(v == 0 for v in A)
p_num = sum(v > 0 for v in A)
m_num = sum(v < 0 for v in A)

if p_num + m_num < K:
    print(0)
    exit()

if p_num == 0 and m_num >= K and K % 2 == 1:
    if z_num > 0:
        print(0)
    else:
        x = sorted([v for v in A if v < 0], reverse=True)
        ans = 1
        n = len(x)
        for i in range(K):
            ans = ans * x[i] % MOD
        print(ans)
    exit()

x = []
for v in A:
    if v != 0:
        x.append((abs(v), v // abs(v)))
    else:
        x.append((0, 0))
x.sort()

plus = []
minus = []
for i in range(K):
    v, s = x.pop()
    if s >= 0:
        plus.append(v)
    else:
        minus.append(v)


if len(minus) % 2 != 0 and 0 not in v:
    p_cand = MOD
    m_cand = MOD
    while x:
        v, s = x.pop()
        if s == 1 and p_cand == MOD:
            p_cand = v
        elif s == -1 and m_cand == MOD:
            m_cand = v

    if p_cand == MOD and m_cand != MOD and plus:
        plus.pop()
        minus.append(m_cand)
    elif m_cand == MOD and p_cand != MOD and minus:
        minus.pop()
        plus.append(p_cand)
    elif p_cand != MOD and m_cand != MOD and plus and minus:
        p_org = plus.pop()
        m_org = minus.pop()
        if p_org * p_cand > m_org * m_cand:
            plus.append(p_org)
            plus.append(p_cand)
        else:
            minus.append(m_org)
            minus.append(m_cand)


ans = 1
for v in plus:
    ans = ans * v % MOD
for v in minus:
    ans = ans * (-v) % MOD
print(ans)


### FIXED CODE ###

N, K, *A = map(int, open(0).read().split())

MOD = 10 ** 9 + 7
s = []  # v >= 0
t = []  # v < 0
for i in range(N):
    if A[i] < 0:
        t.append(A[i])
    else:
        s.append(A[i])
        
ok = False  # ans > 0
if len(s) > 0:
    if N == K:
        ok = len(t) % 2 == 0
    else:
        ok = True
else:
    ok = K % 2 == 0

ans = 1
if not ok:
    x = sorted(A, key=lambda x: abs(x))
    for i in range(K):
        ans = ans * x[i] % MOD
else:
    s.sort()
    t.sort(key=lambda x: abs(x))
    if K % 2 == 1:
        ans = ans * s.pop() % MOD
        
    p = []
    while len(s) >= 2:
        x = s.pop() * s.pop()
        p.append(x)
    
    while len(t) >= 2:
        x = t.pop() * t.pop()
        p.append(x)

    p.sort(reverse=True)
    for i in range(K // 2):
        ans = ans * p[i] % MOD
    
print(ans)
def masucnt(masu,i,j):
  s="."
  try:
    s=masu[i][j]
  except:
    s=""
  return 1 if s=="#" else 0

h,w=map(int,input().split())
masu=[""]*h

for i in range(h):
  masu[i]=input().strip()

for i in range(h):
  for j in range(len(masu[i]))
    n=0
    s=masu[i][j]
    if s=="#"
      print("#",end="")
    else:
      n+=masucnt(masu,i-1,j-1)
      n+=masucnt(masu,i-1,j)
      n+=masucnt(masu,i-1,j+1)
      n+=masucnt(masu,i,j-1)
      n+=masucnt(masu,i,j+1)
      n+=masucnt(masu,i+1,j-1)
      n+=masucnt(masu,i+1,j)
      n+=masucnt(masu,i+1,j+1)
      print(n,end="")
  print("")
    

### FIXED CODE ###

def masucnt(masu,i,j):
  if i<0 or j<0:
    return 0
  s="."
  try:
    s=masu[i][j]
  except:
    s=""
  return 1 if s=="#" else 0

h,w=map(int,input().split())
masu=[""]*h

for i in range(h):
  masu[i]=input().strip()

for i in range(h):
  for j in range(len(masu[i])):
    n=0
    s=masu[i][j]
    if s=="#":
      if j==(len(masu[i])-1):
        print("#")
      else:
        print("#",end="")
    else:
      n+=masucnt(masu,i-1,j-1)
      n+=masucnt(masu,i-1,j)
      n+=masucnt(masu,i-1,j+1)
      n+=masucnt(masu,i,j-1)
      n+=masucnt(masu,i,j+1)
      n+=masucnt(masu,i+1,j-1)
      n+=masucnt(masu,i+1,j)
      n+=masucnt(masu,i+1,j+1)
      if j==(len(masu[i])-1):
        print(n)
      else:
        print(n,end="")
n = int(input())
pre = list(map(int, input().split()))
ino = list(map(int, input().split()))

d = []
root = pre[1]
pre = iter(pre).__next__

def dfs(l, r):
    global d
    if l >= r:
        return
    c = pre()
    m = ino.index(c)
    dfs(l, m)
    dfs(m+1, r)
    d += [c]
    
dfs(0, len(ino))
print(*d)



### FIXED CODE ###

n = int(input())
pre = list(map(int, input().split()))
ino = list(map(int, input().split()))

d = []
root = pre[0]
pre = iter(pre).__next__

def dfs(l, r):
    global d
    if l >= r:
        return
    c = pre()
    m = ino.index(c)
    dfs(l, m)
    dfs(m+1, r)
    d += [c]
    
dfs(0, len(ino))
print(*d)
N, M, X, Y = (int(i) for i in input().split())
l_x = [int(x) for x in input().split()]
l_y = [int(y) for y in input().split()]

if max(l_x) => min(l_y):
    print('War')
else:
    print('No War')

### FIXED CODE ###

N, M, X, Y = (int(i) for i in input().split())
l_x = [int(x) for x in input().split()]
l_y = [int(y) for y in input().split()]

l_x.append(X)
l_y.append(Y)
if max(l_x) >= min(l_y):
    print('War')
else:
    print('No War')
from sys import exit
from math import gcd
n = int(input())
a = list(map(int, input().split()))
g = gcd(a[0], a[1])
for i in range(2, n):
	g = gcd(g, a[i])
if g > 1:
	print("not coprime")
	exit()

MAX = 32
nxt = [i for i in range(MAX)]
for i in range(2, MAX):
	if nxt[i] < i:
		continue
	for j in range(i, MAX, i):
		nxt[j] = min(nxt[j], i)

fac = set()
ok = True
for x in a:
	tmp = set()
	while x > 1:
		tmp.add(nxt[x])
		x //= nxt[x]
	for p in tmp:
		if p in fac:
			ok = False
			break
		fac.add(p)
	if not ok:
		break
print("pairwise coprime" if ok else "setwise coprime")

### FIXED CODE ###

from sys import exit
from math import gcd
n = int(input())
a = list(map(int, input().split()))
g = gcd(a[0], a[1])
for i in range(2, n):
	g = gcd(g, a[i])
if g > 1:
	print("not coprime")
	exit()

MAX = 1000001
nxt = [i for i in range(MAX)]
for i in range(2, MAX):
	if nxt[i] < i:
		continue
	for j in range(i, MAX, i):
		nxt[j] = min(nxt[j], i)

fac = set()
ok = True
for x in a:
	tmp = set()
	while x > 1:
		tmp.add(nxt[x])
		x //= nxt[x]
	for p in tmp:
		if p in fac:
			ok = False
			break
		fac.add(p)
	if not ok:
		break
print("pairwise coprime" if ok else "setwise coprime")
import numpy as np
n=[]
line=''

### FIXED CODE ###

n=[]
line=''
while line != [0,0]:
    line=list(map(int,input().split()))
    n.append(line)
for i in range(len(n)-1):
    print('%d %d'%(n[i][0] if n[i][0]<=n[i][1] else n[i][1],n[i][0] if n[i][0]>=n[i][1] else n[i][1]))
N, M = map(int, input().split())
P=[]
for i in range(N):
  x,y=map(int, input().split())
  P.append([x,y])
C=[]
for i in range(M):
  a,b=map(int, input().split())
  C.append([a,b])

for p in P:
  mind=10000000
  for j in range(M):
    d=abs(p[0]-C[j][0])+abs(p[1]-C[j][1])
    if d<mind:
      ans=j+1
      mind=d
  print(ans)



### FIXED CODE ###

N, M = map(int, input().split())
P=[]
for i in range(N):
  x,y=map(int, input().split())
  P.append([x,y])
C=[]
for i in range(M):
  a,b=map(int, input().split())
  C.append([a,b])

for p in P:
  mind=10**18
  for j in range(M):
    d=abs(p[0]-C[j][0])+abs(p[1]-C[j][1])
    if d<mind:
      ans=j+1
      mind=d
  print(ans)
n = int(input())
table = input().split()
print("{} {} {}".format(max(table[n]),min(table[n]),sum(table[n]))))


### FIXED CODE ###

n = input()
table = list(map(int,input().split()))
print("{} {} {}".format(min(table),max(table),sum(table)))
a,b = map(int,input().split())
s = b
p = 0.0
for i in range(1,a+1):
	tmp = 1.0/a
	now = i
	while now < b:
		now = now*2
        tmp = tmp/2
	p = p+tmp
print(%.12f%p)

  
  
  
  
  

### FIXED CODE ###

a,b = map(int,input().split())
s = b
p = 0.0
for i in range(1,a+1):
	tmp = 1.0/a
	now = i
	while now < b:
		now = now*2
		tmp = tmp/2
	p = p+tmp
print(p)
n=int(input())

mod=10**9+7

pp={}
pp_k=set([])

pm={}
pm_k=set([])

from fractions import gcd


for _ in range(n):
    a,b=map(int,input().split())
    tmp=gcd(a,b)
    a=a//tmp
    b=b//tmp

    if a*b>0:
        if (a,b) in pp_k:
            pp[(a,b)]+=1
        else:
            pp[(a,b)]=1
            pp_k.add((a,b))
    else:
        if (a,b) in pm_k:
            pm[(a,b)]+=1
        else:
            pm[(a,b)]=1
            pm_k.add((a,b))

result=pow(2,n,mod)-1

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = mod #割る数
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

#print(pp_k,pm_k)
for item in pp_k:

    tmp=0

    a,b=item[0],item[1]
    cnt_pp=pp[item]
    aa=-1*a
    bb=b
    cnt_pm=0
    hoge=(bb,aa)
    #print(hoge)
    if hoge in pm_k:
        #print("Yes")
        cnt_pm+=pm[hoge]
    aa=a
    bb=-1*b
    hoge=(bb,aa)
    if hoge in pm_k:
        cnt_pm+=pm[hoge]
    #print(item,cnt_pm)
    if cnt_pm>0:
        tmp+=pow(2,max(0,n-cnt_pm-cnt_pp),mod)*(pow(2,cnt_pp,mod)-1)*(pow(2,cnt_pp,mod)-1)
        #print(pow(2,max(0,n-cnt_pm-cnt_pp),mod),(pow(2,cnt_pp,mod)-1),(pow(2,cnt_pp,mod)-1))
        result-=tmp

print(result%mod)
    

    

### FIXED CODE ###

n=int(input())

mod=10**9+7

#初期値が0の辞書
from collections import defaultdict
pp = defaultdict(lambda: 0) 
pm = defaultdict(lambda: 0) 

def seiki(x,y):
    tmp=gcd(x,y)
    return (x//tmp,y//tmp)

from math import gcd
zero=0
for _ in range(n):
    a,b=map(int,input().split())

    if a==0 and b==0:
        zero+=1
    elif a*b>0:
        tmp=seiki(abs(a),abs(b))
        pp[tmp]+=1
    elif a==0:
        pp[(1,0)]+=1
    elif b==0:
        pm[(1,0)]+=1
        pp[(1,0)]+=0
    else:
        tmp=seiki(abs(b),abs(a))
        pm[tmp]+=1
        pp[tmp]+=0
#print(pm)
#print(pp)
result=1
for key in pp.keys():
    pp_v=pp[key]
    pm_v=pm[key]
    result*=(pow(2,pm_v,mod)+pow(2,pp_v,mod)-1)
    result%=mod

print((result-1+zero)%mod)
s = int(input())
count = 0
for i in ragen(len(s)):
    if (i % 2 == 0 and s[i] ==0) or (i % 2 ==1 and s[i] == 1):
        pass
    else:
        count += 1
print(min[c,len(s) - c])

### FIXED CODE ###

s = [int(i) for i in input()]
count = 0
l = len(s)
for i in range(l):
    if (i % 2 == 0 and s[i] ==0) or (i % 2 ==1 and s[i] == 1):
        pass
    else:
        count += 1
print(min([count,l - count]))
from bisect import bisect
from itertools import accumulate


def solve(v, w):
    vl = bisect(table, v)
    wl = bisect(table, w)
    if vl > wl:
        for i in range(vl - wl):
            v = (v + m) // n
    elif wl < vl:
        for i in range(wl - vl):
            w = (w + m) // n
    while v != w:
        if v > w:
            v, w = w, v
        w = (w + m) // n
    return v


n, q = map(int, input().split())
m = n - 2
table, k = [], 1
while True:
    table.append(k)
    k *= n
    if k > 1e9:
        break
table = accumulate(table)

print('\n'.join(map(str, (solve(*map(int, input().split())) for _ in range(q)))))


### FIXED CODE ###

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

if n == 1:
    def solve(v, w):
        return min(v, w)
else:
    def solve(v, w):
        while v != w:
            if v > w:
                v, w = w, v
            w = (w + n - 2) // n
        return v

print('\n'.join(map(str, (solve(*map(int, input().split())) for _ in range(q)))))
P=[]
C=[]
point=1001    #全問題数

D,G=map(int,input().split())
for i in range(D):
    p,c= map(int,input().split())
    P.append(p)
    C.append(c)

#とりあえず全部解くor解かないで目標スコアを超えるか超えないかを考える


for i in range(2**D) :
    score=0
    solve=0
    needproblem=0
    for j in range(D) :                  #全正解した大問をスコアに変換
        if (i>>j) & 1 :
            score+=P[j]*100*(j+1)+C[j]
            solve+=P[j]
    if score>=G :
        point=min(point,solve)

#ぎりぎりスコアが届いていない場合、1問も解かなかった問題の中で最も一題あたりの点が高い問題だけ解いてみる
#中途半端に大問を解ききるのが１種類以下でも目標に届く場合もあるという予想
    elif score<G :
        rest=G-score
        for j in range(D) :
            if (~i>>D-j) & 1 :
                needproblem=D-j+1
            sum=needproblem*100*(P[needproblem-1]-1)
            if rest>sum :            #1問も解かなかった問題の中で最も一題あたりの点が高い問題を解いても届かないのでやり直し
                rest-=sum
                solve+=P[needproblem-1]-1
            elif rest<=sum :
                resolve=solve+rest//(needproblem*100)
                point=min(point,resolve)
                continue

print(point)

### FIXED CODE ###

D,G=map(int,input().split())
# bit全探索で、全問解く問題の組み合わせをすべて試す
 
scores=[None]*D
for i in range(D):
  p,c=map(int,input().split())
  # 一問の得点、問題数、ボーナス、全てといたときの得点
  scores[i]=[(i+1)*100,p,c,((i+1)*100)*p+c]
 
# あとあとのために点数高い順に並べる
scores=sorted(scores,key=lambda x:x[0])[::-1]
 
# 全問とく組み合わせに対して、最小の問題数
ans=D*100
for i in range(2**D):
  total=0
  solve=0
  for j in range(D):
    if (i>>j)&1:
      # 全問とく問題のボーナスを足していく
      total+=scores[j][3]
      solve+=scores[j][1]
  if total>=G:
    if ans>solve:
      ans=solve
    continue
  rest=G-total
  for j in range(D):
    if (i>>j)&1==0:
      point=scores[j][0]
      num=scores[j][1]-1 # 全問とかないので1減らす
      if point*num<rest:
        rest-=point*num
        solve+=num
      else:
        solve+=(rest//point+(rest%point>0))
        rest=0
    if rest<=0 and ans>solve:
      ans=solve
  
print(ans)
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd (a, b)

n=int(input())
a=list(map(int,input().split()))
l=1
for i in range(0,n):
    l=lcm(l,a[i])
ans=0
for i in range(0,n):
    ans=ans+l/a[i]
print (int(ans%(10**9+7)))

### FIXED CODE ###

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd (a, b)

n=int(input())
a=list(map(int,input().split()))
l=1
for i in range(0,n):
    l=lcm(l,a[i])
ans=0
for i in range(0,n):
    ans=ans+l//a[i]
print (ans%(10**9+7))
import sys
from collections import deque, defaultdict
from itertools import combinations, permutations
from heapq import heapify, heappop, heappush

def solve():
    input = sys.stdin.readline
    H, N = map(int, input().split())
    M = [tuple(int(a) for a in input().split()) for _ in range(N)]
    DP = [1000000000] * (H + 2) #ダメージiを与えるのに必要な最小MP, DP[H+1]はH以上のダメージを与えた場合
    DP[0] = 0
    for i, m in enumerate(M):
        a, b = m
        for j in range(H-a+1): DP[j + a] = min(DP[j + a], DP[j] + b)
        for j in range(H-a+1, H): DP[H + 1] = min(DP[H + 1], DP[j] + b)
    print(min(DP[H], DP[H + 1]))

    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys
from collections import deque, defaultdict
from itertools import combinations, permutations
from heapq import heapify, heappop, heappush

def solve():
    input = sys.stdin.readline
    H, N = map(int, input().split())
    M = [tuple(int(a) for a in input().split()) for _ in range(N)]
    DP = [1000000000] * (H + 2) #ダメージiを与えるのに必要な最小MP, DP[H+1]はH以上のダメージを与えた場合
    DP[0] = 0
    for i, m in enumerate(M):
        a, b = m
        for j in range(max(H-a+1, 0)): DP[j + a] = min(DP[j + a], DP[j] + b)
        for j in range(max(H-a+1, 0), H): DP[H + 1] = min(DP[H + 1], DP[j] + b)
    print(min(DP[H], DP[H + 1]))

    return 0

if __name__ == "__main__":
    solve()
s = input()
K = int(input())

sub = []
for i in range(1, len(s)+1):
    for k in range(len(s)-i+1):
        sub.append(s[k:k+i])

sub = list(set(sub))
sub.sort()
print(sub[k+1])


### FIXED CODE ###

s = input()
K = int(input())

sub = []
for i in range(1, K+1):
    for k in range(len(s)-i+1):
        sub.append(s[k:k+i])

sub = list(set(sub))
sub.sort()
print(sub[K-1])
r = map(int, input())
print(3 * (r ** 2))

### FIXED CODE ###

r = int(input())
print(3*(r**2))
n,m = map(int, input().split())
aa = [0] * m
bb = [0] * m
cc = [0] * m
dd = [0] * m

for i in range(n):
    aa[i], bb[i] = map(int, input().split())
for i in range(m):
    cc[i], dd[i] = map(int, input().split())

distance = []
for i in range(n):
    d = [abs(aa[i] - cc[j]) + abs(bb[i] - dd[j]) for j in range(m)]
    print(d.index(min(d))+1)

### FIXED CODE ###

n,m = map(int, input().split())
aa = [0] * n
bb = [0] * n
cc = [0] * m
dd = [0] * m

for i in range(n):
    aa[i], bb[i] = map(int, input().split())
for i in range(m):
    cc[i], dd[i] = map(int, input().split())

for i in range(n):
    d = [abs(aa[i] - cc[j]) + abs(bb[i] - dd[j]) for j in range(m)]
    print(d.index(min(d))+1)
n=int(input())
m=[]
for c,s,f in map(int,input().split()):
  m.append(0)
  for i in range(len(m)):
    if m[i]>s:
      m[i]=s+((m[i]-s)//f+((m[i]-s)%f>0))*f+c
    else:#m[i]<=s
      m[i]=s+c
m.append(0)
for i in m:
  print(i)

### FIXED CODE ###

n=int(input())
m=[]
for _ in range(n-1):
  c,s,f=map(int,input().split())
  m.append(0)
  for i in range(len(m)):
    if m[i]>s:
      m[i]=s+((m[i]-s)//f+((m[i]-s)%f>0))*f+c
    else:#m[i]<=s
      m[i]=s+c
m.append(0)
for i in m:
  print(i)
n = int(input())
a = int(input())
a%500==b
if (b<=n):
  print("Yes")
else:
  print("No")


### FIXED CODE ###

a = int(input())
n = int(input())
if((a%500)<=n):
  print("Yes")
else:
  print("No")
N,M,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
ans = 0
time = 0
while time < K:
    if not A:
        ans += 1
        if time + B[0]:
            break
        time += B[0]
        B.pop(0)
    elif not B:
        ans += 1
        if time + A[0]:
            break
        time += A[0]
        A.pop(0)
    elif A[0] > K or B[0] > K:
        break
    elif A[0] == B[0]:
        if A[1] > B[1]:
            if time + B[0]:
                break
            time += B[0]
            ans += 1
            B.pop(0)
        elif A[1] < B[1]:
            if time + A[0]:
                break
            time += B[0]
            ans += 1
            A.pop(0)
    elif A[0] > B[0] :
        if time + B[0]:
            break
        time += B[0]
        ans += 1
        B.pop(0)
    elif A[0] < B[0]:
        if time + A[0]:
            break
        time += B[0]
        ans += 1
        A.pop(0)
print(ans)


### FIXED CODE ###

#import sys
N,M,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

a=[0]
b=[0]
for i in range(N):
    a.append(a[i]+A[i])
for j in range(M):
    b.append(b[j]+B[j])
ans = 0
l = M
for k in range(N+1):
    if a[k] > K:
        break
    while b[l] > K - a[k]:
        l -= 1
    ans = max(ans,k+l)
print(ans)
import fractions

N=int(input())
t,a=1,1
for i in range(N):
    T,A=map(int,input().split())
    n=max(fractions.ceil(a/A),fractions.ceil(t/T))
    t,a=n*T,n*A

print(t+a)


### FIXED CODE ###

import fractions

N=int(input())
t,a=1,1
for i in range(N):
    T,A=map(int,input().split())
    n=max(-(-a//A),-(-t//T))
    # n=max(fractions.ceil(a/A),fractions.ceil(t/T))
    t,a=n*T,n*A

print(t+a)
import sys,itertools as o,scipy.sparse as s;_,r,*t=[map(int,i.split())for i in sys.stdin];a,b,c=zip(*t);l=s.csgraph.dijkstra(s.csr_matrix((c,(a,b)),[201]*2),0);print min(sum(int(l[i][j])for i,j in zip(a,a[1:]))for a in o.permutations(r))

### FIXED CODE ###

import sys,itertools as o,scipy.sparse as s;_,r,*t=[map(int,i.split())for i in sys.stdin];a,b,c=zip(*t);l=s.csgraph.dijkstra(s.csr_matrix((c,(a,b)),[201]*2),0);print(min(sum(int(l[i][j])for i,j in zip(a,a[1:]))for a in o.permutations(r)))
A B C = list(map(int, input().split()))
a = A B C
print("Yes" if a[0]== a[2] == 5 and a[1] == 7 else "No")

### FIXED CODE ###

a = list(map(int, input().split()))
print("YES" if a.count(5) == 2 and a.count(7) == 1 else "NO")
import sys

sys.setrecursionlimit(100000)
INF = float('inf')

N = int(sys.stdin.readline())
ABC = [list(map(int, sys.stdin.readline().split())) for _ in range(N - 1)]
Q, K = list(map(int, sys.stdin.readline().split()))
X, Y = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(Q)]))


def dfs(v, a, graph, ret=None):
    ret = ret or {}
    ret[v] = a
    for u, w in graph[v]:
        if u in ret:
            continue
        dfs(u, a + w, graph, ret)
    return ret


#: :type: list of (list of (int, int))
graph = [[] for _ in range(N + 1)]
for a, b, c in ABC:
    graph[a].append((b, c))
    graph[b].append((a, c))

dists = dfs(K, 0, graph)
for x, y in zip(X, Y):
    print(int(dists[x] + dists[y]))


### FIXED CODE ###

import heapq
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

N = int(sys.stdin.readline())
ABC = [list(map(int, sys.stdin.readline().split())) for _ in range(N - 1)]
Q, K = list(map(int, sys.stdin.readline().split()))
X, Y = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(Q)]))


def dijkstra(graph, start):
    """
    TODO: start していしなかったときに全部の距離を知りたい

    マイナスの辺があっちゃダメ
    scipy.sparse.csgraph.dijkstra は内部で使われてるフィボナッチヒープが一部のケースでめっちゃ遅いのであんまり使わないほうがよさげ
    https://atcoder.jp/contests/soundhound2018-summer-qual/submissions/5311823

    :param list of (list of (int, int)) graph:
        graph[from_index]: (to_index, weight)
    :param int start:
    :return:
    """
    dist = [float('inf') for _ in range(len(graph))]
    dist[start] = 0
    heap = []
    heapq.heappush(heap, (0, start))

    while len(heap) > 0:
        w, v = heapq.heappop(heap)
        if w > dist[v]:
            continue
        for u, dw in graph[v]:
            if w + dw < dist[u]:
                dist[u] = w + dw
                heapq.heappush(heap, (w + dw, u))
    return dist


#: :type: list of (list of (int, int))
graph = [[] for _ in range(N + 1)]
for a, b, c in ABC:
    graph[a].append((b, c))
    graph[b].append((a, c))

dists = dijkstra(graph, K)

for x, y in zip(X, Y):
    print(int(dists[x] + dists[y]))
a,b,c=input()
a=int(a)
c=int(c)

if b=='+':
    s=a+c
else:
    s=a-c
print(s)


### FIXED CODE ###

l=input().split()
a=int(l[0])
x=l[1]
b=int(l[2])
if(x=='+'):
    print(a+b)
else:
    print(a-b)
a,b  = map(int, raw_input().split())
A = [map(int, raw_input().split()) for _ in xrange(a)]
b = [input() for _ in x range(b)]
Ab = [sum([A[i][j] * b[j] for j in x range(b)]) for i in x range(a)]
for x in Ab:
    print x

### FIXED CODE ###

a,b  = map(int, raw_input().split())
A = [map(int, raw_input().split()) for _ in xrange(a)]
B = [input() for _ in xrange(b)]
C = [sum([A[i][j] * B[j] for j in xrange(b)]) for i in xrange(a)]
for x in C:
    print x
S=input()
if S[3]==S[4] and S[5]==S[6]:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

S=input()
if S[2]==S[3] and S[4]==S[5]:
  print("Yes")
else:
  print("No")
K = int(input())
S = input()

if (len(S) <= K):
    print(S)
else:
    print(S[:K] + "...")

### FIXED CODE ###

n = input()
N = int(n)

m = N % 10

if (m == 3):
    print("bon")
elif (m == 0 or m == 1 or m == 6 or m == 8):
    print("pon")
else:
    print("hon")
while True:
    n = int(input())
    if n == 0:
        break
    a = [int(input()) for _ in range(n)]
    d = [a[0]]
    for i in range(n):
        if d[0] == 0:
            d[0] += a[i]
        elif a[i] / d[-1] >= 0:
            d[-1] += a[i]
        else:
            d.append(a[i])
            
    if len(d) <= 2:
        print(max(max(d), max(a))
    else:
        if d[0] < 0:
            d.pop(0)
        maxd = max(d)
        for i in range(0, len(d), 2):
            for j in range(i + 1, len(d) + 1, 2):
                maxd = max(maxd, sum(d[i:j]))
        print(maxd)


### FIXED CODE ###

from collections import deque
while True:
    n = int(input())
    if n == 0:break
    a = [int(input()) for _ in range(n)]
    b = deque([0] * n)
    j = 0
    for i in range(n):
        if a[i] * b[j] >= 0:b[j] += a[i]
        else:j += 1;b[j] += a[i]
    if b[0] < 0 and len(b) > 1:b.popleft()
    while b[-1] <= 0 and len(b) > 1:b.pop()
    if len(b) == 1 and b[0] <= 0:print(max(a))
    else:
        m = len(b) // 2 + 1
        v = [[0] * m for _ in range(m)]
        v[0][0] = b[0]
        for i in range(1, m):
            v[0][i] = v[0][i - 1] + b[2 * i] + b[2 * i - 1]
        for i in range(1, m):
            for j in range(i, m):
                v[i][j] = v[i - 1][j] - b[2 * i - 2] - b[2 * i - 1]
        print(max([max(i) for i in v]))
s=input()
if len(s)%2:
	print("No")
elif s[:((len(s)/2)]==s[(len(s)/2):]:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

ln=input()
s=input()
if len(s)%2:
    print("No")
elif s[:(len(s)//2)]==s[(len(s)//2):]:
    print("Yes")
else:
    print("No")