Harryxun/stf_run huggingface dataset:
def euclidean(a,b):
  """
  a >= b
  """
_ = a % b
while 1:
  if b % _ == 0:
    break
  else:
    _ = b % _
  return _

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

a = max(A, B)
b = min(A, B)
e = euclidean(a,b)

by = []
r = int(e ** (1 / 2))
for i in range(1, r + 1):
  if e % i == 0:
    by.append(i)
    j = e // i
    if j != i:
      by.append(j)
by.sort()
print(by[K - 1])


### FIXED CODE ###

def euclidean(a,b):
  _ = a % b
  if _ == 0:
    return b
  else:
    while 1:
      if b % _ == 0 :
        break
      else:
        _ = b % _
    return _
  
A, B, K = map(int, input().split())
 
a = max(A, B)
b = min(A, B)
e = euclidean(a, b)
by = []
r = int(e ** (1 / 2))
 
for i in range(1, r + 1):
  if e % i == 0:
    by.append(i)
    j = e // i
    if j != i:
      by.append(j)
by.sort(reverse = True)
print(by[K - 1])
S = input()
N = len(S)
i = 0
while i < N:
    sig = 0
    S5 = S[i:i+5]
    if S5 == 'dream':
        sig = 1
        if S[i+5:i+7] == 'er' and S[i+7] != 'a':
            i += 2
        i += 5
    elif S5 == 'erase':
        sig = 1
        if S[i+5:i+6] == 'r':
            i += 1
        i += 5
    if sig == 0:
        sig = 2
        Answer = 'NO'
        break
if sig != 2:
    Answer = 'YES'
print(Answer)

### FIXED CODE ###

S = input()
N = len(S)
i = 0
while i < N:
    sig = 0
    S5 = S[i:i+5]
    if S5 == 'dream':
        sig = 1
        if S[i+5:i+7] == 'er' and S[i+7:i+8] != 'a':
            i += 2
        i += 5
    elif S5 == 'erase':
        sig = 1
        if S[i+5:i+6] == 'r':
            i += 1
        i += 5
    if sig == 0:
        sig = 2
        Answer = 'NO'
        break
if sig != 2:
    Answer = 'YES'
print(Answer)
k. x = map(int, input().split())
if k*500 >= x:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

k, x = map(int, input().split())
if k*500 >= x:
  print('Yes')
else:
  print('No')
a,b=map(int,input().split())
print(a//b,a%b,'{0:10.5f}'.format(a/b'))


### FIXED CODE ###

a,b=map(int,input().split())
print(a//b,a%b,'{0:10.5f}'.format(a/b))
n, y = map(int(input()))


def helper(n,y):
    for ten in range(y,-1,-1):

        for five in range(y-ten, -1,-1):
            
            sum = 10000*ten + 5000*five + 1000*one

            if n < sum:
                continue

            if n == sum:
                return('{} {} {}'.format(ten,five,one))

            else:
                return ('-1 -1 -1')

    return('-1 -1 -1')

print(helper(n,y))

### FIXED CODE ###

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

def helper(n,y):

    for ten in range(n,-1,-1):
        for five in range(n-ten, -1,-1):


            one = n-ten-five
            sum = 10000*ten + 5000*five + 1000*one

            if y == sum:
                return('{} {} {}'.format(ten,five,one))


    return('-1 -1 -1')

print(helper(n,y))
import numpy as np
import math
from functools import reduce

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

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


N = int(input())
T = np.array(sorted([int(input()) for _ in range(N)]))
print(lcm(*T))


### FIXED CODE ###

import numpy as np


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

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

N = int(input())
T = sorted([int(input()) for _ in range(N)])

ans = 1
for t in T:
    ans = lcm_base(ans,t)
print(ans)
import collections
n=int(input())
if n==1:
  print(0)
  exit()
b=int(n**0.5)
i=2
l=[]
while i<=b:
  if n%i==0:
    l.append(i)
    n=n//i
  else:
    i+=1
if n>b:
  l.append(n)
c=collections.Counter(l)
v=list(c.values())
ans=0
for vv in v:
  wa=1
  s=1 
  while True:
    if vv<wa:
      break
    s+=1
    wa+=s
  ans+=(s-1)
print(ans)

### FIXED CODE ###

from decimal import Decimal
a,b=map(Decimal,input().split())
print(int(a*b))
import collections
import numpy as np

n = int(input())
l = input().split()
v = [ int(s) for s in l ]

#n = 4
npv = np.array( v, dtype=np.int32)
#npv = np.array( [3,1,3,2], dtype=np.int32)
npv_dic = {}
npv_dic['even'] = npv[0::2]
npv_dic['odd']  = npv[1::2]

#print('n = ', n)
#print('npv = ', npv)
#print('npv_dic[\'even\'] = ', npv_dic['even'])
#print('npv_dic[\'odd\']  = ', npv_dic['odd'])

dict0 = collections.Counter(npv_dic['even'])
dict1 = collections.Counter(npv_dic['odd'])

list0 = list(dict0.items())
list1 = list(dict1.items())

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

#print(list0[0] ,list1[0])
#print(list0[1] ,list1[1])

if list0[0][0] == list1[0][0]:
    if list0[0][1] == list1[0][1]:
        if list0[1][1] > list1[1][1]:
            del list0[0]
        else:
            del list1[0]
    elif list0[0][1] > list1[0][1]:
        del list1[0]
    else:
        del list0[0]
#print(list0[0] ,list1[0])
#print(list0[1] ,list1[1])

if list0.__len__() != 0:
    change0 = n//2 - list0[0][1]
else:
    change0 = n//2
change1 = n//2 - list1[0][1]
#print('change:', change0, change1)

print(change0 + change1)


### FIXED CODE ###

import collections
import numpy as np

n = int(input())
l = input().split()
v = [ int(s) for s in l ]

#n = 4
npv = np.array( v, dtype=np.int32)
#npv = np.array( [3,1,3,2], dtype=np.int32)
npv_dic = {}
npv_dic['even'] = npv[0::2]
npv_dic['odd']  = npv[1::2]

#print('n = ', n)
#print('npv = ', npv)
#print('npv_dic[\'even\'] = ', npv_dic['even'])
#print('npv_dic[\'odd\']  = ', npv_dic['odd'])

dict0 = collections.Counter(npv_dic['even'])
dict1 = collections.Counter(npv_dic['odd'])

list0 = list(dict0.items())
list1 = list(dict1.items())

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

#print(list0[0] ,list1[0])
#print(list0[1] ,list1[1])

if list0[0][0] == list1[0][0]:
    if (list0[0][1] == list1[0][1]) and \
        (list0.__len__() > 1) and (list0.__len__() > 1):
        if list0[1][1] > list1[1][1]:
            del list0[0]
        else:
            del list1[0]
    elif list0[0][1] > list1[0][1]:
        del list1[0]
    else:
        del list0[0]
#print(list0[0] ,list1[0])
#print(list0[1] ,list1[1])

if list0.__len__() != 0:
    change0 = n//2 - list0[0][1]
else:
    change0 = n//2
change1 = n//2 - list1[0][1]
#print('change:', change0, change1)

print(change0 + change1)
from functools import *
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def acinput():
    return list(map(int, input().split(" ")))


def II():
    return int(input())


directions = np.array([[1, 0], [0, 1], [-1, 0], [0, -1]])
directions = list(map(np.array, directions))

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact


def serch(x, count):
    #print("top", x, count)

    for d in directions:
        nx = d+x
        # print(nx)
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)
                continue
            if field[nx[0]][nx[1]] == "#":
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)

    return count


N = int(input())
A = []
for i in range(N):
    A.append(II())


if A[0] >0:
    print(-1)
    sys.exit()

for i in range(1, N):
    if A[i]-A[i-1] > 1:
        print(-1)
        sys.exit()

count = 0
x = [0]*N

for i in reversed(range(N)):
    if A[i] != x[i]:
        for j in range(i-A[i], i):
            x[j+1] = x[j]+1
            count += 1


print(count)


### FIXED CODE ###



from functools import *
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def acinput():
    return list(map(int, input().split(" ")))


def II():
    return int(input())




N = int(input())
A = []
for i in range(N):
    A.append(II())


if A[0] >0:
    print(-1)
    sys.exit()

for i in range(1, N):
    if A[i]-A[i-1] > 1:
        print(-1)
        sys.exit()

count = 0
x = [0]*N

for i in range(0,N-1):
    if A[i]+1==A[i+1]:
        count+=1
    else:
        count+=A[i+1]

""" for i in reversed(range(N)):
    if A[i] != x[i]:
        for j in range(i-A[i], i):
            x[j+1] = x[j]+1
            count += 1

 """
print(count)
a,v=input().split()
b,w=input().split()
t=int(input())
A=int(a)
B=int(b)
W=int(w)
V=int(v)
-10^9<=A,B<=10^9
1<=V,W<=10^9
1<=t<=10^9
A!=B
x=B-A
y=V-W
z=y/x
if z<=t:
    print('YES')
else:
    print('NO')


### FIXED CODE ###

import random
S=input()
3<=len(S)<=20
x=random.randint(3,len(S))
y=x-3
print(S[y:x])
import itertools
import math

d,g=list(map(int,input().split()))
PC=[list(map(int,input().split())) for _ in range(d)]
ans=[]

for i in range(d):
  for j in itertools.combinations(range(d),i):
    score,pro1=0,0
    for k in j:
      score += (PC[k][1] + (k+1) * 100 * PC[k][0])
      pro1 += PC[k][0]
    for k in range(d):
      pro2 = pro1
      if score >= g:
        ans.append(pro2)
      elif k in j:
        continue
      p=math.ceil((g-score) / ((k+1) * 100))
      if 0 < p < PC[k][0]:
        pro2 += p
        ans.append(pro2)
        
print(min(ans))

### FIXED CODE ###

import itertools
import math

d,g=list(map(int,input().split()))
PC=[list(map(int,input().split())) for _ in range(d)]
ans=[]

for i in range(d+1):
  for j in itertools.combinations(range(d),i):
    score,pro1=0,0
    for k in j:
      score += (PC[k][1] + (k+1) * 100 * PC[k][0])
      pro1 += PC[k][0]
    for k in range(d):
      pro2 = pro1
      if score >= g:
        ans.append(pro2)
      elif k in j:
        continue
      p=math.ceil((g-score) / ((k+1) * 100))
      if 0 < p < PC[k][0]:
        pro2 += p
        ans.append(pro2)
        
print(min(ans))
N,M =map(int,input().split())
H = list(map(int,input().split()))
ab = [map(int, input().split()) for _ in range(M)]
a, b = map(list, zip(*ab))

cnt = 0

for i in range(N):
  Boolean = True
  # aの中からiへ続く道があるかを全件検索
  for j,k in enumerate(a):
    # aの中にiがあり、その道先の展望台の山が高かったらiは破棄して次へ
    if (i == k and H[i] <= H[b[j] - 1]):
      Boolean = False
      break

  for j,k in enumerate(b):
    # bの中にiがあり、その道先の展望台の山が高かったらiは破棄して次へ
    if (i == k and H[i] <= H[a[j]]):
      Boolean = False
      break
  # abを全件調査してセーフだった場合にcntをあげる
  if(Boolean):
    cnt += 1
print(cnt)

### FIXED CODE ###

N,M =map(int,input().split())
H = list(map(int,input().split()))
ab = [map(int, input().split()) for _ in range(M)]
a, b = map(list, zip(*ab))

cnt = 0
removeList = []

for i in range(len(a)):
  if (H[a[i]-1] > H[b[i]-1]):
    removeList.append(b[i])
  elif (H[a[i]-1] < H[b[i]-1]):
    removeList.append(a[i])
  else:
    removeList.append(a[i])
    removeList.append(b[i])

set(removeList)
print(N - len(set(removeList)))
def main():
    nm = map(int, raw_input().split())
    A = []
    B = []
    flag = False
    for i in range(nm[0]):
        A.append(raw_input())
    for i in range(nm[1]):
        B.append(raw_input())

    for i in range(nm[0]):
        for j in range(nm[0]):
            if j + nm[1] <= nm[0]:
                for k in range(nm[1]):
                    for l in range(nm[1]):
                        if(A[i+k][j+l] == B[k][l]):
                            flag = True
                        else:
                            flag = False
                            break 
                    if flag == False:
                        break
            if flag:
                 break
        if flag:
            break
    if flag:
        return "yes"
    else:
        return "no"    
print main()

### FIXED CODE ###

def main():
    nm = map(int, raw_input().split())
    A = []
    B = []
    flag = False
    for i in range(nm[0]):
        A.append(raw_input())
    for i in range(nm[1]):
        B.append(raw_input())

    for i in range(nm[0]):
      if i + nm[1] <= nm[0]:
        for j in range(nm[0]):
            if j + nm[1] <= nm[0]:
                for k in range(nm[1]):
                    for l in range(nm[1]):
                        if(A[i+k][j+l] == B[k][l]):
                            flag = True
                        else:
                            flag = False
                            break 
                    if flag == False:
                        break
            else:
                break
            if flag:
                 break
        if flag:
            break
      else:
          break
       
    if flag:
        return "Yes"
    else:
        return "No"    
print main()
a = input()
if a='Sunny':
  print('Cloudy')

### FIXED CODE ###

a = input()
if a=='Sunny':
  print('Cloudy')
elif a=='Cloudy':
  print('Rainy')
elif a=='Rainy':
  print('Sunny')
N,M = int(a) for a in input().split()
print(N)
print(M)


### FIXED CODE ###

input_str =  input().split()
N = int(input_str[0])
M = int(input_str[1])

if N == M:
  print("Yes")
else:
  print("No")
import math
a, b, c, d = list(map(int, input().split()))


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


def search(n, i, j):
    l = lcm(i, j)
    return n - int(n / i) - int(n / j) + int(n / l)


print(search(b, c, d) - search(a - 1, c, d))


### FIXED CODE ###

import fractions
a, b, c, d = list(map(int, input().split()))


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


def search(n, i, j):
    l = lcm(i, j)
    return n - n // i - n // j + n // l


print(search(b, c, d) - search(a - 1, c, d))
i = 1
x = int(input())
while:
    if y == 0:
        break
    print(f 'Case {i}: {x[y]}')
    i += 1



### FIXED CODE ###

case_num = 1

while True:
    tmp_num = int(input())
    if tmp_num == 0:
        break
    else:
        print("Case %d: %d" % (case_num,tmp_num))
        case_num += 1
#素因数分解
def prime_factorization(N):
    n=N
    a=2
    prime_factor=[]
    while a**2<=n:
        while n%a==0:
            prime_factor.append(a)
            n//=a
        a+=1
    if n>1:
        prime_factor.append(n)
    return prime_factor


N=int(input())

a=1
b=N//a
dis=abs(b-a)

for i in range(1,int(N**0.5)+1):
    if N%i==0:
        _a=i
        _b=N//i
        _dis=abs(_b-_a)
        if _dis<dis:
            a=_a
            b=_b
            dis=_dis

print(a-1+b-1)

### FIXED CODE ###

A,B=map(int,input().split())
if A>9 or B>9:
  print(-1)
  exit()
print(A*B)
n = int(input())
l = list(map(int,input().split())

print(min(l),max(l),sum(l))


### FIXED CODE ###

n = int(input())
ns = list([int(i) for i in input().split()])
print(min(ns),max(ns),sum(ns))
s = raw_input()
ans = 0
for i in range(0, 4):
	if s[i] = '+': ans = ans + 1
	else: ans = ans - 1

print ans

### FIXED CODE ###

s = raw_input()
ans = 0
for i in range(0, 4):
	if s[i] == '+': ans = ans + 1
	else: ans = ans - 1

print ans
n,m = map(int,input().split())
base = [int(input()) for i in range(m)]
count = 0
now = 0
i= 0
j = 0

dp = [0]*(n+1)
if 1 == base[j]:
  dp[1] = 0
  if j < m-1:
    j = j + 1
else:
  dp[1] = 1

dp[0] = 1

for i in range(2,n+1):
  if not (i == base[j]):
    dp[i] = dp[i-1] + dp[i-2]
  elif i == base[j]:
    if j < m-1:
      j = j+1
  
  
print(int(dp[n]%1000000007))

### FIXED CODE ###

n,m = map(int,input().split())
base = [int(input()) for i in range(m)]
i= 0
j = 0

dp = [0]*(n+1)
if m == 0:
  base = [n+1]

if 1 == base[j]:
  dp[1] = 0
  if j < m-1:
    j = j + 1
else:
  dp[1] = 1

dp[0] = 1

for i in range(2,n+1):
  if not (i == base[j]):
    dp[i] = dp[i-1] + dp[i-2]
  elif i == base[j]:
    if j < m-1:
      j = j + 1
  
  
print(int(dp[n]%1000000007))
import numpy as np
H, W, M = map(int, input().split())
HW = []
A = np.zeros((H, W), dtype='int')

for _ in range(M):
    h, w = map(int, input().split())
    h, w = h - 1, w - 1
    HW.append((h, w))
    A[h, w] = 1
# print(f'{HW=}')
# print(f'{A=}')

arr = A.sum(axis=0)
col_idx = np.where(arr == arr.max())[0]
col_max = arr.max()

arr = A.sum(axis=1)
row_idx = np.where(arr == arr.max())[0]
row_max = arr.max()

# print(A.sum(axis=0).argsort()[-1])

for r in row_idx:
    for c in col_idx:
        if A[r, c] == 0:
            ans = col_max + row_max
            print(ans)
            exit()
ans = col_max + row_max - 1
print(ans)


### FIXED CODE ###

import numpy as np
H, W, M = map(int, input().split())

C = [0] * W
R = [0] * H
S = set()
for _ in range(M):
    h, w = map(int, input().split())
    h, w = h - 1, w - 1  # 0-indexed
    C[w] += 1
    R[h] += 1
    S.add((h, w))

col_max = max(C)
col_idx = [i for i in range(W) if C[i] == col_max]
row_max = max(R)
row_idx = [i for i in range(H) if R[i] == row_max]

ans = col_max + row_max
for r in row_idx:
    for c in col_idx:
        if not (r, c) in S:
            print(ans)
            exit()
print(ans - 1)
mod = 10**9+7
 
fact = [1,1]
finv = [1,1]
inv = [0,1]
 
for i in range(2,2*10**5+5):
    fact.append((fact[-1]*i)%mod)
    inv.append((inv[mod%i]*(mod-mod//i))%mod)
    finv.append((finv[-1]*inv[-1])%mod)
 
def nCr(n,r,mod):
      
    return fact[n]*finv[r]*finv[n-r]%mod

n = int(input())
e = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    e[a-1].append(b-1)
    e[b-1].append(a-1)

numl = [0]*n
resl = [0]*n
def dfs(x,pre):
    num = 0
    res = 1
    for nex in e[x]:
        if nex == pre:
            continue
        dfs(nex,x)
        num += numl[nex]
        res *= nCr(num,numl[nex],mod)*resl[nex]
        res %= mod
    numl[x] = num+1
    resl[x] = res

    return 

dfs(0,-1)

ans = [0]*n
ans[0] = resl[0]
def dfs2(x,pre):
    
    for nex in e[x]:
        if nex == pre:
            continue
        pres = [resl[x], numl[x], resl[nex], numl[nex]]
        resl[x] *= pow(nCr(numl[x]-1,numl[nex],mod)*resl[nex],mod-2,mod)
        resl[x] %= mod
        numl[x] -= numl[nex]
        resl[nex] *=  nCr(numl[x]+numl[nex]-1,numl[x],mod)*resl[x]
        resl[nex] %= mod
        numl[nex] += numl[x]
        ans[nex] = resl[nex]
        dfs2(nex,x)
        resl[x], numl[x], resl[nex], numl[nex] = pres
    return
dfs2(0,-1)
for i in ans:
    print(i)

### FIXED CODE ###


import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
mod = 10**9+7
 
fact = [1,1]
finv = [1,1]
inv = [0,1]
 
for i in range(2,2*10**5+5):
    fact.append((fact[-1]*i)%mod)
    inv.append((inv[mod%i]*(mod-mod//i))%mod)
    finv.append((finv[-1]*inv[-1])%mod)
 
def nCr(n,r,mod):
      
    return (fact[n]*finv[r])%mod*finv[n-r]%mod

n = int(input())
e = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    e[a-1].append(b-1)
    e[b-1].append(a-1)

numl = [0]*n
resl = [0]*n
def dfs(x,pre):
    num = 0
    res = 1
    for nex in e[x]:
        if nex == pre:
            continue
        dfs(nex,x)
        num += numl[nex]
        res *= nCr(num,numl[nex],mod)*resl[nex]
        res %= mod
    numl[x] = num+1
    resl[x] = res

    return 

dfs(0,-1)

ans = [0]*n
ans[0] = resl[0]
def dfs2(x,pre):
    
    for nex in e[x]:
        if nex == pre:
            continue
        pres = [resl[x], numl[x], resl[nex], numl[nex]]
        resl[x] *= pow(nCr(numl[x]-1,numl[nex],mod)*resl[nex],mod-2,mod)
        resl[x] %= mod
        numl[x] -= numl[nex]
        resl[nex] *=  nCr(numl[x]+numl[nex]-1,numl[x],mod)*resl[x]
        resl[nex] %= mod
        numl[nex] += numl[x]
        ans[nex] = resl[nex]
        dfs2(nex,x)
        resl[x], numl[x], resl[nex], numl[nex] = pres
    return
dfs2(0,-1)
for i in ans:
    print(i)
import numpy as np

n = int(input())
v = np.array(list(map(int, input().split())))
c = np.array(list(map(int, input().split())))
p = v-c
for i in p:
    if i>0:
        ans+=i

print(ans)


### FIXED CODE ###

import numpy as np

n = int(input())
v = np.array(list(map(int, input().split())))
c = np.array(list(map(int, input().split())))
p = v-c
ans = sum([i for i in p if i>0])
print(ans)
money = for(int(i) in i = input().sprit())
mod = money[0] % 500
if money[1] >= mod:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

money = int(input())
coins = int(input())
mod = money % 500
if coins >= mod:
  print("Yes")
else:
  print("No")
N = int(math.sqrt(int(input())))

print(N*N)

### FIXED CODE ###

import math
N = int(math.sqrt(int(input())))
print(N*N)
l=input()
mod=pow(10,9)+7

def func(li):
  if '0' not in li:
    return pow(3,len(li),mod)
  elif len(li)==1:
    if li=='1':
      return 3
    else:
      return 1
  elif li[0]=='0':
    return func(li[1:])%mod
  else:
    ret=(2*func(li[1:]))%mod
    ret+=func('1'*(len(li)-1))%mod
    return ret%mod
print(func(l))


### FIXED CODE ###

l=input()
n=len(l)
mod=pow(10,9)+7
import sys
sys.setrecursionlimit(10**7)
#dp1,dp2=[0]*n,[0]*n
dp1,dp2=0,1
for i in range(n):
  if l[i]=='0':
    dp1*=3
  else:
    dp1*=3
    dp1+=dp2
    dp2*=2
  dp1%=mod
  dp2%=mod
print((dp1+dp2)%mod)
from heapq import *

T = [[10**18 for _ in range(2451)] for _ in range(N)]

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

N, M, S = tuple(map(int, input().split()))

for i in range(M):
  U, V, A, B = tuple(map(int, input().split()))
  U -= 1
  V -= 1
  act[U] += [(V, A, B)]
  act[V] += [(U, A, B)]

for i in range(N):
  C, D = tuple(map(int, input().split()))
  act[i] += [(i, -C, D)]

que = [(0, 0, S)]

while que:
  (currentT, n, coins) = heappop(que)
  for m, cost, t in act[n]:
    # もし「払える金額で」「最小時間T[移動先][所持金]を更新できるとき」に値を更新、キューに状態を追加。
    if coins >= cost and currentT + t < T[m][min(2450, coins - cost)]:
      T[m][min(2450, coins - cost)] = currentT + t
      heappush(que, (currentT + t, m, min(2450, coins - cost)))

for i in range(1, N):
  print(min(T[i]))

### FIXED CODE ###

from heapq import *

N, M, S = tuple(map(int, input().split()))

T = [[10**18 for _ in range(2451)] for _ in range(N)]

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

for i in range(M):
  U, V, A, B = tuple(map(int, input().split()))
  U -= 1
  V -= 1
  act[U] += [(V, A, B)]
  act[V] += [(U, A, B)]

for i in range(N):
  C, D = tuple(map(int, input().split()))
  act[i] += [(i, -C, D)]

que = [(0, 0, S)]

while que:
  (currentT, n, coins) = heappop(que)
  for m, cost, t in act[n]:
    # もし「払える金額で」「最小時間T[移動先][所持金]を更新できるとき」に値を更新、キューに状態を追加。
    if coins >= cost and currentT + t < T[m][min(2450, coins - cost)]:
      T[m][min(2450, coins - cost)] = currentT + t
      heappush(que, (currentT + t, m, min(2450, coins - cost)))

for i in range(1, N):
  print(min(T[i]))
a = int(input())

b = []

p = 0
pp = 0
ppp = 0

for i in range(a):
    b.append(list(map(int,input().split())))
if a == 1:
    print(b[0][0],b[0][1],b[0][2])
b.sort(b,key=lambda x:-x[2])
else:
    for i in range(0,101,-1):
        for j in range(0,101,-1):
            for k in range(a):
                if k == 0:
                 p = abs(b[k][0] - i) + abs(b[k][1]-j)+b[k][2]
            else:
                if max(0,p - abs(b[k][0]-i)- abs(b[k][1]-j)) != b[k][2]:
                    pp = 1
        if pp == 0:
            ppp = 1
            break
        else:
            pp = 0
    if ppp == 1:
        print(i,j,p)
        break



### FIXED CODE ###

a = int(input())

b = []

p = 0
pp = 0
ppp = 0

for i in range(a):
    b.append(list(map(int,input().split())))
b.sort(key=lambda x:-x[2])
for i in range(0,101):
    for j in range(0,101):
        for k in range(a):
            if k == 0:
                p = abs(b[k][0] - i) + abs(b[k][1]-j)+b[k][2]
            else:
                if max(0,p - abs(b[k][0]-i)- abs(b[k][1]-j)) != b[k][2]:
                    pp = 1
        if pp == 0:
            ppp = 1
            break
        else:
            pp = 0
    if ppp == 1:
        print(i,j,p)
        break
N = int(input)
S = [input() for i in range(n)]
for v in ['AC', 'WA', 'TLE', 'RE']:
  print('{} x {}'.format(v, s.count(v))
	

### FIXED CODE ###

N = int(input())
S = [input() for i in range(N)]
for v in ['AC', 'WA', 'TLE', 'RE']:
	print('{0} x {1}'.format(v, S.count(v)))
a,b = -1e11,1e11
for _ in int(input()):
    data = int(input())
    a,b = max(a,c-b),min(b,c)
print(a)


### FIXED CODE ###

a,b = -1e11,1e11
for _ in range(int(input())):
    c = int(input())
    a,b = max(a,c-b),min(b,c)
print(a)
import math
n=input().split()
a = int(n[0])*100
b=int(n[1]) *100

ans = a*b

print(ans/100)


### FIXED CODE ###

import math
from decimal import Decimal
n=input().split()
a = int(n[0])
b=Decimal(n[1])
ans = a*b

print(int(ans))