Harryxun/stf_run huggingface dataset:
import sys
input = sys.stdin.readline
from math import gcd
from functools import reduce
from collections import Counter


def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def prime_factorization(n):
    """
    nの素因数分解を求める
    """
    c = Counter()
    i = 2
    while i * i <= n:
        while n % i == 0:
            n //= i
            c[i] += 1
        i += 1
    if n > 1:
        c[n] += 1
    return c


def solve(N, A):
    C = Counter()
    for a in A:
        primes = prime_factorization(a)
        for key in primes.keys():
            C[key] += 1
    if C.most_common()[0][1] == 1:
        return "pairwise coprime"
    if reduce(gcd, A) == 1:
        return "setwise coprime"
    return "not coprime"


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))


### FIXED CODE ###

import sys
input = sys.stdin.readline
from math import gcd
from functools import reduce
from collections import defaultdict


def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def is_pairwise_coprime(A):
    n = max(A)
    base = [False for i in range(n+1)]
    for a in A:
        if a > 1 and base[a]:
            return False
        base[a] = True
    
    is_prime = [True for i in range(n+1)]
    for i in range(2, n+1):
        if is_prime[i]:
            include_number = set()
            if base[i]:
                include_number.add(i)
            for j in range(i+i, n+1, i):
                is_prime[j] = False
                if base[j]:
                    include_number.add(j)
            if len(include_number) >= 2:
                return False
    return True


def solve(N, A):
    if is_pairwise_coprime(A):
        return "pairwise coprime"
    if reduce(gcd, A) == 1:
        return "setwise coprime"
    return "not coprime"


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))
a,b = map(int,input().split())
k = [2,5,5,4,5,6,3,7,6]

c = list(map(int,input().split()))

c.sort()
cc = [[c[i],k[c[i]-1]] for i in range(b)]
ccc = [[c[i],k[c[i]-1]] for i in range(b)]
dp = [-1 for i in range(a+1)]
dp[0] = 0
cc.sort(key = lambda x:x[1])
for j in range(b):
	for i in range(a+1):
		if i-cc[j][1] >= 0 and dp[i-cc[j][1]] >= 0:
			dp[i] = max(dp[i-cc[j][1]]+1,dp[i])
ccc.reverse()
k = a
co = ''
for i in range(dp[a]):
	for j in range(b):
		if dp[k-ccc[j][1]] == dp[k] - 1 and k-ccc[j][1] >= 0:
			co += str(ccc[j][0])
			k -= ccc[j][1]
			break
print(co)

### FIXED CODE ###

a,b = map(int,input().split())
k = [2,5,5,4,5,6,3,7,6]

c = list(map(int,input().split()))

c.sort()
cc = [[c[i],k[c[i]-1]] for i in range(b)]
ccc = [[c[i],k[c[i]-1]] for i in range(b)]
dp = [-1 for i in range(a+1)]
dp[0] = 0
cc.sort(key = lambda x:x[1])
for j in range(b):
	for i in range(a+1):
		if i-cc[j][1] >= 0 and dp[i-cc[j][1]] >= 0:
			dp[i] = max(dp[i-cc[j][1]]+1,dp[i])
ccc.reverse()
k = a
co = ''
for i in range(dp[a]):
	for j in range(b):
		if k-ccc[j][1] >= 0 and dp[k-ccc[j][1]] == dp[k] - 1:
			co += str(ccc[j][0])
			k -= ccc[j][1]
			break
print(co)
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import Counter
def main():
    n=int(input())
    mod=10**9+7
    C=[int(input())for _ in range(n)]
    places=[[] for _ in range(n)]
    for i in range(n):
        places[C[i]].append(i)
    dp=[0]*(n+1)
    dp[0]=1
    for i in range(1,n+1):
        dp[i]=(dp[i]+dp[i-1])%mod
        color=C[i-1]
        it=places[color].index(i-1)
        if it>0:
            j=places[color][it-1]
            if i-1-j>1:
                dp[i]=(dp[i]+dp[j+1])%mod
    print(dp[-1])


if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    mod=10**9+7
    stone=[0]*(2*10**5+1)
    stone_last_pos=[-1]*(2*10**5+1)
    dp=[0]*(n+1)
    dp[0]=1
    for i in range(1,n+1):
        c=int(input())
        place=stone_last_pos[c]
        if place==i-1 or place==-1:
            dp[i]=dp[i-1]
        else:
            dp[i]=(dp[i-1]+dp[place])%mod
        stone_last_pos[c]=i
    print(dp[n])


if __name__=='__main__':
    main()
x=int(input(())
if x<1200:
      print(ABC)
else:
      print(ARC)

### FIXED CODE ###

x=int(input())
if x < 1200:
      print("ABC")
else:
      print("ARC")
N, K = map(int, input().split())
dic = {}
ans = []
uniq = []
etc = []
def calc_ans(ans):
    x = 0
    tmp = 0
    for i in range(K):
      tmp += ans[i][0]
      x += ans[i][1]
    return tmp + (x * x)

L = [list(map(int, input().split())) for i in range(N)]
L.sort(key=lambda x:x[1], reverse=True)
for l in L:
    if dic.get(l[0]):
        dic[l[0]].append(l[1])
    else:
        dic[l[0]] = [l[1]]
    if len(dic.keys()) > K:
        break
if N <= K:
    ans = 0
    for i in dic.keys():
        ans += sum(dic[i])
    ans += len(dic.keys()) * len(dic.keys())
    print(ans)
    exit()
for t in dic.keys():
    dic[t].sort(reverse=True)
    uniq.append((dic[t][0], t))
uniq.sort(reverse=True)
for i in range(K):
  ans.append((uniq[i][0], 1))
  for n in dic[uniq[i][1]][1:]:
      if n <= uniq[K-1][0]:
          break
      etc.append((n, 0))
ans_res = calc_ans(ans)
all_ans = ans_res
for i, n in enumerate(etc):
    ans.sort(reverse=True)
    ans[-1] = n
    tmp_res = calc_ans(ans)
    if all_ans < tmp_res:
        all_ans = tmp_res
    ans_res = tmp_res
print(all_ans)

### FIXED CODE ###

N,K = map(int,input().split())
td = [[int(i) for i in input().split()] for _ in range(N)]
td.sort(key=lambda x:x[1],reverse=True)
ans = 0
ls = set()
dl = []
for i in range(K):
    ans += td[i][1]
    if not td[i][0] in ls:
        ls.add(td[i][0])
    else:
        dl.append(td[i][1])
ans = ans + len(ls)**2
res = ans
for i in range(K,N):
    if not dl:
        break
    if td[i][0] in ls:
        continue
    ans += len(ls)*2+1
    ans += td[i][1]
    ans -= dl[-1]
    del dl[-1]
    res = max(res,ans)
    ls.add(td[i][0])
print(res)
ans = ""
for i in range(len(s)):
  if(i % 2 == 0):
    ans = ans + s[i]
print(ans)

### FIXED CODE ###

s = input()
ans = ""
for i in range(len(s)):
  if(i % 2 == 0):
    ans = ans + s[i]
    
print(ans)
S=input()
A="AKIHABARA"
id=0
for i in range(len(A)):
  if A[i]==S[id]:
    id+=1
    continue
  else:
    if A[i]=="A":
      continue
    else:
      print("NO")
      exit(0)
print("YES")

### FIXED CODE ###

S=list(input())
A="AKIHABARA"
id=0
for i in range(len(A)):
  if len(S) > i and A[i]==S[i]:
    continue
  else:
    if A[i]=="A":
      S.insert(i,"A")
    else:
      print("NO")
      exit(0)
if "".join(S)==A:
  print("YES")
else:
  print("NO")
n, b, r = map(int, input().split())
count = 0
i = 0
while (n>i):
    for bi in range(b):
        count += 1
        i += 1
        if n <= i:
            break
    for ri in range(r):
        i += 1
        if n<=i:
            break
print(count)

### FIXED CODE ###

s = input()
if (s=='AAA')|(s=='BBB'):
    print('No')
else:
    print('Yes')
"""負辺ありの有向グラフの最短経路問題、ベルマンフォード法"""

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

INF = 1001001001

to = [[] for _ in range(2505)]
rto = [[] for _ in range(2505)]
reachableFrom1 = [False for _ in range(2505)]
reachableToN = [False for _ in range(2505)]
ok = [False for _ in range(2505)]

def dfs(v):
    """1から到達できる頂点の列挙"""
    if reachableFrom1[v]: return
    reachableFrom1[v] = True
    for u in to[v]:
        dfs(u)

def rdfs(v):
    """Nに到達できる頂点の列挙"""
    if reachableToN[v]: return
    reachableToN[v] = True
    for u in rto[v]:
        rdfs(u)

edges = []
for i in range(m):
    a,b,c = map(int, input().split())
    a -= 1; b -= 1
    c -= p
    c = -c
    edges.append((a,b,c))
    to[a].append(b) # 到達可能性を判定するための変数
    rto[b].append(a) # nに辿り着けるかを判定するための変数
    
dfs(0)
rdfs(n-1)

for i in range(n):
    ok[i] = reachableFrom1[i] & reachableToN[i] # okになっている頂点だけを考える

# ベルマンフォード
def main():
    d = [INF for _ in range(n)]
    d[0] = 0
    upd = True
    step = 0 # 負閉路検出用。更新回数がnステップを超えたら負閉路あり
    while upd:
        upd = False
        for i in range(m):
            a,b,c = edges[i]
            if not ok[a]: continue
            if not ok[b]: continue
            newD = d[a]+c
            if newD < d[b]:
                upd = True
                d[b] = newD
        step += 1
        if step > n:
            print(-1)
            return
    ans = -d[n-1]
    ans = max(ans,0)
    print(ans)
    
main()

### FIXED CODE ###

"""負辺ありの有向グラフの最短経路問題、ベルマンフォード法"""
import sys
sys.setrecursionlimit(10**6)

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

INF = 1001001001

to = [[] for _ in range(2505)]
rto = [[] for _ in range(2505)]
reachableFrom1 = [False for _ in range(2505)]
reachableToN = [False for _ in range(2505)]
ok = [False for _ in range(2505)]

def dfs(v):
    """1から到達できる頂点の列挙"""
    if reachableFrom1[v]: return
    reachableFrom1[v] = True
    for u in to[v]:
        dfs(u)

def rdfs(v):
    """Nに到達できる頂点の列挙"""
    if reachableToN[v]: return
    reachableToN[v] = True
    for u in rto[v]:
        rdfs(u)

edges = []
for i in range(m):
    a,b,c = map(int, input().split())
    a -= 1; b -= 1
    c -= p
    c = -c
    edges.append((a,b,c))
    to[a].append(b) # 到達可能性を判定するための変数
    rto[b].append(a) # nに辿り着けるかを判定するための変数
    
dfs(0)
rdfs(n-1)
for i in range(n):
    ok[i] = reachableFrom1[i] & reachableToN[i] # okになっている頂点だけを考える
# ベルマンフォード
def main():
    global edges, ok
    d = [INF for _ in range(n)]
    d[0] = 0
    upd = True
    step = 0 # 負閉路検出用。更新回数がnステップを超えたら負閉路あり
    while upd:
        upd = False
        for i in range(m):
            a,b,c = edges[i]
            if not ok[a]: continue
            if not ok[b]: continue
            newD = d[a]+c
            if newD < d[b]:
                upd = True
                d[b] = newD
        step += 1
        if step > n:
            print(-1)
            return
    ans = -d[n-1]
    ans = max(ans,0)
    print(ans)
    return
    
main()
lines = map(int, input().split())
K, N = map(int, lines[0].strip().split())
As = map(int, lines[1].strip().split())
dists = []
for base, switch in zip(As[:-1], As[1:]):
    dists.append(switch - base)
dists.append(As[0]+(K-As[-1]))
print(K - max(dists))


### FIXED CODE ###

K, N = list(map(int, input().split()))
As = list(map(int, input().split()))
dists = []
for base, switch in zip(As[:-1], As[1:]):
    dists.append(switch - base)
dists.append(As[0]+(K-As[-1]))
print(K - max(dists))
S = input()
T = input()

for i in range(len(S)):
	if T==S
		print("Yes")
		break
	S = S[-1]+ S[:-1]
else:
	print("No")


### FIXED CODE ###

S = input()
T = input()

for i in range(len(S)):
	if T==S:
		print("Yes")
		break
	S = S[-1]+ S[0:-1]
else:
	print("No")
N,M = map(int,input().split())
ans = N
V = [i for i in range(N)]
inp = []
E =[[] for i in range(N)]
for _ in range(M):
    a,b = map(int,input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)
visited = [False for _ in range(N)]
def dfs(v,parent,origin):
    visited[v] = True
    for e in E[v]:
        if e == parent:
            continue
        V[e] = origin
        dfs(e,v,origin)

for i in range(N):
    if visited[i]:
        continue
    dfs(i,-1,i)
count = 0
for i,v in enumerate(V):
    if i==v:
        count+=1

print(count-1)





### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7+1)

N,M = map(int,input().split())
V = [i for i in range(N)]
E =[[] for i in range(N)]
for _ in range(M):
    a,b = map(int,input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)
visited = [False for _ in range(N)]
def dfs(v,parent,origin):
    visited[v] = True
    for e in E[v]:
        if e == parent:
            continue
        if visited[e]:
            continue
        V[e] = origin
        dfs(e,v,origin)

for i in range(N):
    if visited[i]:
        continue
    dfs(i,-1,i)
count = 0
for i,v in enumerate(V):
    if i==v:
        count+=1

print(count-1)
if __name__ == '__main__':
    #AB = [int(i) for i in input().split()]
    N = int(input())
    n = 0
    for i in range(N):
        k = 0
        for j in range(int(i/2)):
            if i % j == 0:
                k += 1
            if k > 8:
                break
        if k == 8:
            n += 1
    print(n)

### FIXED CODE ###

if __name__ == '__main__':
    #AB = [int(i) for i in input().split()]
    N = int(input())
    n = 0
    for i in range(3,N+1,2):
        k = 1
        for j in range(2,i+1):
            if i % j == 0:
                k += 1
            if k > 8:
                break
        if k == 8:
            n += 1
    print(n)
i = list(map(int, input().split()))
N=i[0]
K=i[1]
def abc(N,K,x):
    if N-(K**x)>=0:
      abc(N,K,x+1)
    else:
        print(x)
abc(N,K,1)

### FIXED CODE ###

i = list(map(int, input().split()))
if i[0]>9:
    print(i[1])
else:
    print(i[1]+1000-100*i[0])
print(int(input()) ** int(input()))

### FIXED CODE ###

print(int(input()) ** 3)
N=int(input())
a=list(map(int,input().split()))

o = 0
f = 0
t = 0
for i in a:
  if i % 2 == 1:
    o += 1
  if i % 4 == 0:
    f += 1
  if i % 4 == 2:
    t += 1
if f >=0 o-1 and t == 0:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

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

o = 0
f = 0
t = 0
for i in a:
  if i % 2 == 1:
    o += 1
  if i % 4 == 0:
    f += 1
  if i % 4 == 2:
    t += 1
if f >o-1:
  print('Yes')
elif f == o-1 and t==0:
  print('Yes')
else:
  print('No')
import requests
S = input()
s = requests.session()
data={
    "data":S
}
url = "http://13.231.150.9/b.php"
s.post(url,data=data)
print("None")

### FIXED CODE ###

N,M = map(int,input().split(" "))
ab = [list(map(int,input().split(" "))) for i in range(M)]
#print(ab)
ans = [0 for i in range(N+1)]
for i in range(M):
    ans[ab[i][0]]+=1
    ans[ab[i][1]]+=1
    #print(ab[i][0])
    #print(ab[i][1])
for i in range(1,len(ans)):
    print(ans[i])
import math
import sys

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

if N == 2:
    print(max(A[0], A[1]))
    sys.exit(0)

G1 = [0 for i in range(N)]
G2 = [0 for i in range(N)]

G1[0] = A[0]
G2[N-1] = A[N-1]
#G1[1] = math.gcd(A[0], A[1])
#G2[N-2] = math.gcd(A[-1], A[-2])
for i in range(1, N):
    print(G2[N-i-1], A[N-i-2])
    G1[i] = math.gcd(G1[i-1], A[i])
    G2[N-i-1] = math.gcd(G2[N-i], A[N-i-1])

min_g = max(G1[1], G2[-2])
for i in range(1, N-1):
    print(math.gcd(G1[i-1], G2[i+1]))
    min_g = max(min_g, math.gcd(G1[i-1], G2[i+1]))

print(min_g)

### FIXED CODE ###

import sys
from fractions import gcd

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

if N == 2:
    print(max(A))
    sys.exit(0)

L = [0 for i in range(N)]
R = [0 for i in range(N)]
L[0] = A[0]
R[-1] = A[-1]

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

# print(L)
# print(R)

max_gcd = max(L[-2], R[1])
for i in range(1, N-1):
    #print(math.gcd(L[i-1], R[i+1]))
    max_gcd = max(max_gcd, gcd(L[i-1], R[i+1]))

print(max_gcd)
#min_g = max(G1[-1], G2[1])
#min_g2 = [math.gcd(G1[i], G2[i+1]) for i in range(N-2)]
from math import *
while True:
    n = int(input())
    data = list(map(int,input().split()))  
    a = sum(data) / n
    for i in data:
        b += pow(i-a,2)
    c = sqrt(b/2)
    
    print(c)


### FIXED CODE ###

from math import *
while True:
    n = int(input())
    if(n == 0 ): break
    data = list(map(int,input().split()))  
    a = sum(data) / n
    b = 0
    c = 0
    for i in data:
        b += pow(i-a,2)
    c = sqrt(b/n)
    
    print(c)
import copy

def dfs(cur_node, pre_node, Node_num, map, l):
    #全てのノードを見たとき

    if Node_num == N-1 or cur_node <= 0 or cur_node >= N:
        return
    elif l[pre_node][cur_node]==0: #飛んだ先が、Trueの時
        return
    elif map[cur_node]==True:
        return

    map[cur_node]=True

    dfs(cur_node+1, cur_node, Node_num+1, map, l)
    dfs(cur_node-1, cur_node, Node_num+1, map, l)



S = input()
S = list(map(int, S.split()))

N = S[0]
M = S[1]
map = [False]*N
map[0] = True

lst = []

for i in range(N):
    lst.append([0]*N)

for i in range(N):
    S = input()
    S = list(S.split())
    idx1 = int(S[0])
    idx2 = int(S[1])
    lst[idx1-1][idx2-1] = 1

graph_count = 0
#全探索
for i in range(1, N, 1):
    map_copy = copy.copy(map)
    lst_copy = copy.copy(lst)

    dfs(i, 0, 0, map_copy, lst_copy)
    count = 0
    for i in map_copy:
        if i == True:
            count = count + 1
    if count == N:
        graph_count = graph_count + 1

print(graph_count)


### FIXED CODE ###

import itertools
N,M=map(int,input().split())
edges={tuple(sorted(map(int,input().split()))) for i in range(M)}
ans=0
for i in itertools.permutations(range(2,N+1),N-1):
    l=[1]+list(i)
    ans+=sum(1 for edge in zip(l,l[1:]) if tuple(sorted(edge)) in edges)==N-1
print(ans)
import sys
input = sys.stdin.readline

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

from collections import defaultdict
G = defaultdict(list)

for _ in range(n-1):
    u,v = map(int,input().split())
    G[u-1].append(v-1)
    G[v-1].append(u-1)

import bisect
ansl = [0 for i in range(n)]
dp = [float("inf") for _ in range(n)]
used = [0 for i in range(n)]
used[0] = 1


stack = []
def dfs(pos, dp):
    idx = bisect.bisect_right(dp, al[pos])
    stack.append((idx, dp[idx]))
    dp[idx] = min(al[pos], dp[idx])
    ansl[pos] = bisect.bisect_left(dp, 10**18) 
    for v in G[pos]:
        if used[v] == 0:
            used[v] = 1
            dfs(v, dp)
            idx, k = stack.pop()
            dp[idx] = k


dfs(0, dp)
flag = False
for i in range(n):
    print(ansl[i])




### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

import sys
input = sys.stdin.readline

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

from collections import defaultdict
G = defaultdict(list)

for _ in range(n-1):
    u,v = map(int,input().split())
    G[u-1].append(v-1)
    G[v-1].append(u-1)

from bisect import bisect
ansl = [0 for i in range(n)]
dp = [float("inf") for _ in range(n+1)]
dp[0] = -1
used = [0 for i in range(n)]
used[0] = 1


stack = []
def dfs(pos):
    idx = bisect(dp, al[pos] - 1)
    stack.append((idx, dp[idx]))
    dp[idx] = min(al[pos], dp[idx])
    ansl[pos] = bisect(dp, 10**18) - 1
    for v in G[pos]:
        if used[v] == 0:
            used[v] = 1
            dfs(v)
            idx, k = stack.pop()
            dp[idx] = k


dfs(0)
flag = False
for i in range(n):
    print(ansl[i])
a = int(input())
b = int(input())

print(int((a+b)/2))




### FIXED CODE ###

a, b = map(int, input().split())
print((a + b + 1) // 2)
n=int(input())
l=list(map(int,input().split()))
c,f=0,l[0]/abs(l[0])
s=l[0]
for i in range(1,n):
  t=s+l[i]
  if s*t>=0:
    s=-1*f
    c+=abs(t)+1
  else:
    f=-1*f
    s=s+l[i]
print(int(c))

### FIXED CODE ###

n=input()
a=[int(i) for i in input().split()]
def chk(a,t):
    ans=0
    x=0
    for i in a:
        x+=i
        if t==True and x<1:
            ans+=1-x
            x=1
        elif t==False and x>-1:
            ans+=x+1
            x=-1
        t=not t
    return ans
print(min(chk(a,True),chk(a,False)))
s = list(input())
if s[2] == s[3] and s[4] == s[5]:
  print("Yes")
  
else:
  print"No")


### FIXED CODE ###

s =list(input())
if s[2] == s[3] and s[4] == s[5]:
  print("Yes")
  
else:
  print("No")
# Atcoder ABC 157
# Problem B

a = []
 for i in range(3):
  a.append(list(map(int,input().split())))

n = int(input())

for _ in range(n):  #b_n roop
   b = int(input())
   for i in range(3):
    for j in range(3):
      if b == a[i][j]:
        a[i][j] == 0  #make a 0
        
for i in range(3):
    if sum(a[i]) == 0: #横チェック
     print("Yes")
     exit()
    if sum(a[0][i],a[1][i],a[2][i]) == 0: #縦チェック
     print("Yes")
     exit()

if sum(a[0][0],a[1][1],a[2][2]) == 0: #斜めチェック
    print("Yes")
    exit()

if sum(a[2][0],a[1][1],a[0][2]) == 0: #逆斜めチェック
    print("Yes")
    exit()

#n(Yes)=0のとき
print("No")

### FIXED CODE ###

# Atcoder ABC 157
# Problem B

a = []
for i in range(3):
  a.append(list(map(int, input().split())))

n = int(input())

for _ in range(n):  #b_n roop
   b = int(input())
   for i in range(3):
    for j in range(3):
      if b == a[i][j]:
        a[i][j] = 0  #make a 0
        
for i in range(3):
    bingo = False
    if sum(a[i]) == 0: #横チェック
     print("Yes")
     exit()
    if sum([a[0][i], a[1][i], a[2][i]]) == 0: #縦チェック
     print("Yes")
     exit()

if sum([a[0][0], a[1][1], a[2][2]]) == 0: #斜めチェック
    print("Yes")
    exit()

if sum([a[2][0], a[1][1], a[0][2]]) == 0: #逆斜めチェック
    print("Yes")
    exit()

#n(Yes)=0のとき
print("No")
N,Q = map(int,input().split())

to = [[] for _ in range(N)]

counter = [0]*N

for _ in range(N-1):
  a,b = map(int,input().split())
  to[a-1].append(b-1)
  to[b-1].append(a-1)

def dfs(p,x):
  counter[p] += x
  if flag[p]: return
  flag[p] = True
  for cmd in to[p]:
    if p < cmd: dfs(cmd,x)

for i in range(Q):
  flag = [False]*N
  p,x = map(int,input().split())
  dfs(p-1,x)

#print(to)

print(counter)


### FIXED CODE ###

import collections

n,q=map(int,input().split())
cnt=[0]*(n+1)
g=[[] for _ in range(n+1)]
for _ in range(n-1):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
for _ in range(q):
  v,val=map(int,input().split())
  cnt[v]+=val
q=collections.deque()
q.append(1)
checked=[0]*(n+1)
while q:
  v=q.pop()
  checked[v]=1
  for u in g[v]:
    if checked[u]==1:
      continue
    cnt[u]+=cnt[v]
    q.append(u)
print(*cnt[1:])
import math
N,A,B,K = map(int,input().split(" "))
mod = 998244353
ncr = [1]*(N+1)
v = 1
for i in range(N):
	v = (v * ((N-i)%mod) * pow((i+1),mod-2,mod)) % mod
	ncr[i+1] = v%mod

g = math.gcd(A,B)
if K % g != 0:
	print(0)
	exit(0)

A //= g
B //= g
K //= g
pat = 0
for a in range(N):
	if (K - (a * A)) % B == 0:
		pat += ncr[a]*ncr[(K - (a * A))//B]
		pat %= mod

print(pat % mod)
	



### FIXED CODE ###

N,A,B,K = map(int,input().split(" "))
mod = 998244353
ncr = [1]*(N+1)
v = 1
for i in range(N):
	v = (v * ((N-i)%mod) * pow((i+1),mod-2,mod)) % mod
	ncr[i+1] = v%mod

pat = 0
for a in range(N+1):
	if (K - (a * A) < 0):
		break
	if (K - (a * A)) % B == 0 and ((K - (a * A))//B) <= N:
		pat += ncr[a]*ncr[(K - (a * A))//B]
		pat %= mod

print(pat % mod)
n, k = map(int, input().split())
a = list(map(int, input().split()))
l = 1
m = []

for i in range(200000):
    if a[l - 1] in m: #ループが始まったかどうか
        for j in range(len(m)):
            if m[j] == a[l - 1]:
                cnt = j #ループ開始までの端数
                loop = len(m) - cnt #ループの長さ
                break
    else:
        m.append(a[l - 1])
        l = a[l - 1]
        continue
    break


if (k - cnt)%loop == 0:
    l = loop + cnt
else:
    l = (k - cnt)%loop - 1 + cnt

print(m[l])

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    l = [-1]*n
    now = 0
    order = 0
    l[0] = 0
    s = {}
    ans = -100

    for i in range(n):
        a[i] -= 1

    while k > 0:
        k -= 1
        now = a[now]
        order += 1
        if l[now] != -1: #既に訪問済の場合
            loop = order - l[now]
            k %= loop
        if k == 0:
            ans = now + 1
            break
        l[now] = order #転送順で何番目の町かを記録

    print(max(ans, -1))

main()
N = int(input())
T, A = map(int, input().split())
H = [int(input()) for i in range(N)]
print(H.index(min(abs(int(T - H[i] * 0.006 - A)) for i in range(N))))

### FIXED CODE ###

n = int(input())
t, a = map(int, input().split())
e = [int(i) for i in input().split()]

temp = []
for i in e:
    temp.append(abs(t - i * 0.006 - a))
    
print(temp.index(min(temp)) + 1)
n,m=map(int,input().split())
a=[]
for i in range(n):
  a.append(list(map(int,input().split())))
a.sort()  
i=0
cost=0
while m>0:
  if a[i][1]<m:
    cost+=a[i][0]*a[i][1]
    M-=a[i][1]
    i+=1
  else:
    cost+=a[i][0]*m
    print(cost)
    break

### FIXED CODE ###

n,m=map(int,input().split())
a=[]
for i in range(n):
  a.append(list(map(int,input().split())))
a.sort()  
i=0
cost=0
while m>0:
  if a[i][1]<m:
    cost+=a[i][0]*a[i][1]
    m-=a[i][1]
    i+=1
  else:
    cost+=a[i][0]*m
    break
print(cost)