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

N = int(input())
a = list(map(int, input().split()))
b = 1
for i in range(N):
  b *= a[i]
  if 0 in a:
    b = 0
    break
  elif b > 10 ** 18:
    b = 'out'
    break
if b == 'out':
  print(-1)
else:
  print(b)


### FIXED CODE ###

import sys
n = input()
list_num =list(map(int,input().split()))
output = 1
if 0 in list_num:
    print(0)
    sys.exit()
for i in list_num:
    output = output * i
    if output > 10 ** 18:
        print(-1)
        sys.exit()
print(output)
### BUGGY CODE ###

import math

N,M = map(int,input().split())
A = M//N
L = []
flag = False
if (A <= 3*(10**7)+8*(10**6)):
  for i in range(1,A+1):
    if (M%(A+1-i) == 0):
      flag = True
      break
  if flag:
    print(A+1-i)
else:
  for i in range(1,3*(10**7)+8*(10**6)):
    if (M%i == 0):
      L.append(i)
  print(max(L))

### FIXED CODE ###

import math

N,M = map(int,input().split())
A = M//N
L = []
for i in range(1,int(math.sqrt(M))+1):
  if (M%i == 0 and i <= A):
    L.append(i)
    if (M//i <= A):
      L.append(M//i)
print(max(L))
### BUGGY CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))

dp = [0]*N

for i in range(1,N):
    dp[i] = min(dp[i-j] + abs(h[i] - h[i-j]) for j in range(1,K+1) if i-j >= 0)
print(dp[-1])

### FIXED CODE ###

def main2(N,h,K):
    dp = [0] * N
    for i in range(1,N):
        dp[i] = min([dp[j] + abs(h[i] - h[j]) for j in range(max(0, i-K), i)])
    return dp[-1]

N, K = map(int, input().split())
h = list(map(int, input().split()))
print(main2(N,h,K))
### BUGGY CODE ###

# from pprint import pprint
# import math
# import collections

n = int(input())
# n, k = map(int, input().split(' '))
# a = list(map(int, input().split(' ')))
a = []
for i in range(n):
    a.append(int(input()))

l = []
for _a in a:
    if _a in l:
        l.remove(_a)
    else:
        l.append(_a)

print(len(l))

### FIXED CODE ###

# from pprint import pprint
# import math
# import collections

n = int(input())
# n, k = map(int, input().split(' '))
# a = list(map(int, input().split(' ')))
a = []
for i in range(n):
    a.append(int(input()))

l = {}
for _a in a:
    if _a in l:
        l.pop(_a)
    else:
        l.update(
            {_a: True}
        )

print(len(l))
### BUGGY CODE ###

mod = 10**9+7

def Pow(a, n):
    if n == 0: return 1
    if n%2 == 0:
        return (Pow(a, n//2))**2%mod
    else:
        return Pow(a, n-1)*a%mod

X, Y = map(int, input().split())
if (X+Y)%3 != 0:
    print(0)
else:
    n = (X+Y)//3
    if X < n or Y < n or X > 2*n or Y > 2*n:
        print(0)
    else:
        k = min(X-n, Y-n)
        R = [0] * (k+1)
        for i in range(1,k+1):
            R[i] = Pow(i, mod-2)
        cmb = [0]*(k+1)
        cmb[0] = 1
        for i in range(k):
            cmb[i+1] = ((cmb[i]*(n-i))%mod)*R[i+1]%mod
        print(cmb[k])

### FIXED CODE ###

mod = 10**9+7

def Pow(a, n):
    if n == 0: return 1
    if n%2 == 0:
        return (Pow(a, n//2))**2%mod
    else:
        return Pow(a, n-1)*a%mod

X, Y = map(int, input().split())
if (X+Y)%3 != 0:
    print(0)
else:
    n = (X+Y)//3
    if X < n or Y < n or X > 2*n or Y > 2*n:
        print(0)
    else:
        k = min(X-n, Y-n)
        R = [0] * (k+1)
        for i in range(1,k+1):
            R[i] = Pow(i, mod-2)
        cmb = [0]*(k+1)
        cmb[0] = 1
        for i in range(k):
            cmb[i+1] = ((cmb[i]*(n-i))%mod)*R[i+1]%mod
        print(cmb[k])
### BUGGY CODE ###

from operator import itemgetter
n, m = map(int, input().split())
bridge = [True] * (n-1)  
ab = []
for _ in range(m):
  a, b = map(int, input().split())
  ab.append((a,b))
ab = sorted(ab, key=itemgetter(1))
count = 0
for a, b in ab:
  if all(bridge[a-1:a-1 + (b-a)]):
    bridge[b-2] = False
    count += 1
print(count)

### FIXED CODE ###

from operator import itemgetter
n, m = map(int, input().split())
bridge = 0
ab = []
for _ in range(m):
  a, b = map(int, input().split())
  ab.append((a,b))
ab = sorted(ab, key=itemgetter(1))
count = 0
for a, b in ab:
  if not a <= bridge <= b:
    count += 1
    bridge = b-1
print(count)
### BUGGY CODE ###

MOD = 10 ** 9 + 7

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

import math

def factoring(k): #kを因数分解し、素因数とその個数を辞書に入れて返す。
    dic = dict()
    n = int(math.sqrt(k))+2
    for i in range(2, n):
        count = 0
        while k%i == 0:
            count += 1
            k = k//i
        if count != 0:
            dic[i] = count
    if k != 1: #sqrt(k)までチェックしてもkが1になっていない --> kが素因数
        dic[k] = 1
    return dic


lst = [0] * (10 ** 6 + 1)
for a in A:
    dic = factoring(a)
    for d in dic:
        lst[d] = max(lst[d], dic[d])

tmp = 1
for index, x in enumerate(lst):
    tmp *= index ** x

# print (tmp)

ans = 0
for a in A:
    ans += tmp // a
    ans %= MOD

print (ans)

### FIXED CODE ###

def main():
    from fractions import gcd

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

    MOD = 10 ** 9 + 7

    tmp = 1
    for a in A:
        tmp *= a // gcd(tmp, a)

    ans = 0
    for a in A:
        ans += tmp // a
    ans %= MOD

    print (ans)

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

#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix
 
from collections import* #defaultdict Counter deque appendleft
import sys
input=sys.stdin.readline  #危険！基本オフにしろ！

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

for s in range(m):
    a,b,c=map(int,input().split())
    d[a].append([b,c])
#print(d)

def BELLMANFORD(point,d,p):
    cost       = {node:-float("inf") for node in range(1,n+1)}
    preference = {node:None         for node in range(1,n+1)}      #最適路のこと
    cost[point]= 0
    for i in range(n-1):                                  #経路の長さは最大n-1であるため
        for now,lis in d.copy().items():
            for nex,c in lis:
                if cost[nex]<cost[now]+c-p:
                    cost[nex]=cost[now]+c-p
                    preference[nex]=now
 
    negative=[0]*n                                        #負閉路の長さは最大nであるため
    
    for i in range(n):                  #閉路判定 negativeの1は閉路に入っている部分を表す
        for now,lis in d.copy().items():
            for nex,c in lis:
                if negative[now-1]==1:
                    negative[nex-1]=1
                if cost[nex]<cost[now]+c-p:
                    cost[nex]=cost[now]+c-p
                    preference[nex]=now
                    negative[now-1]=1
 
    return cost,negative

def main():
    x,y=(BELLMANFORD(1,d,p))
#    print(x,y)
    if y[n-1]==1:
        print(-1)
    else:
        print(max(x[n],0))

    
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input=sys.stdin.readline  #危険！基本オフにしろ！


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

d={}
for s in range(m):
    a,b,c=map(int,input().split())
    if a in d:
        d[a].append((b,c))
    else:
        d[a]=[(b,c)]

#print(d)


def BELLMANFORD(point,d,p):
    cost       = [-float("inf") for node in range(n+1)]  #infじゃないと閉路検出がうまくいかない
    cost[point]= 0
    for i in range(n-1):                                  #経路の長さは最大n-1であるため
        for now,lis in d.items():
            for nex,c in lis:
                if cost[nex]<cost[now]+c-p:
                    cost[nex]=cost[now]+c-p

    negative=[0]*n                                        #負閉路の長さは最大nであるため
    
    for i in range(n):                  #閉路判定 negativeの1は閉路に入っている部分を表す
        for now,lis in d.items():
            for nex,c in lis:
                if negative[now-1]==1:
                    negative[nex-1]=1
                if cost[nex]<cost[now]+c-p:
                    cost[nex]=cost[now]+c-p
                    negative[now-1]=1
 
    return cost,negative

def main():
    x,y=(BELLMANFORD(1,d,p))
    
    if y[n-1]==1:
        print(-1)
    else:
        print(max(x[n],0))

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

N, K = map(int,input().split())


while abs(N-K) < N:
  N = abs(N-K)
  
print(N)

### FIXED CODE ###

N,K = map(int,input().split())

if N % K == 0:
  print(0)
else:
  q = N // K
  d = N - K*q
  print(min(d,abs(d-K)))
### BUGGY CODE ###

H,W = map(int, input().split())
#a = [['#'] * (W+2) for i in range(H+2)]
cnt = [[-5] * (W+2) for i in range(H+2)]
c = 0
fin = 0
for h in range(1,H+1):
    ai = input()
    for w in range(1,W+1):
        #a[h][w] = ai[w-1]
        if ai[w-1] == '#':
            cnt[h][w] = c
            fin += 1
        else:
            cnt[h][w] = -1

            
#print(cnt,fin)
dxy = ([1,0],[0,1],[-1,0],[0,-1])

while fin < H*W:
    for h in range(1,H+1):
        for w in range(1,W+1):
            if cnt[h][w] == c:
                for dx,dy in dxy:
                    if cnt[h+dx][w+dy] == -1:
                        cnt[h+dx][w+dy] = c+1
                        #print(cnt)
                        fin += 1
    c += 1

ans = []
for h in range(1,H+1):
    ans.append(max(cnt[h]))

print(max(ans))

### FIXED CODE ###

from collections import deque
H,W = map(int, input().split())
#a = [['#'] * (W+2) for i in range(H+2)]
cnt = [[-5] * (W+2) for i in range(H+2)]
c = 0
fin = 0
st = deque()
sts = deque()
push, pop = st.append, st.pop
pushs, pops = sts.append, sts.pop
for h in range(1,H+1):
    ai = input()
    for w in range(1,W+1):
        #a[h][w] = ai[w-1]
        if ai[w-1] == '#':
            cnt[h][w] = c
            push([h,w])
            fin += 1
        else:
            cnt[h][w] = -1


dxy = ([1,0],[0,1],[-1,0],[0,-1])

while fin < H*W:
    while st:
        [h,w] = pop()
        for dx,dy in dxy:
            if cnt[h+dx][w+dy] == -1:
                #print(c,fin)
                cnt[h+dx][w+dy] = c+1
                pushs([h+dx,w+dy])
                fin += 1
    c += 1
    while sts:
        [h,w] = pops()
        push([h,w])


print(c)
### BUGGY CODE ###

from sys import stdin
from collections import Counter

lines = stdin.readlines()

N, K, Q = map(int, lines[0].split())
A = [int(i) - 1 for i in lines[1:]]
ans = [0] * N
for a in Counter(A):
    ans[a] += A.count(a)
print("\n".join(("Yes" if Q < K + a
                 else "No" for a in ans)))


### FIXED CODE ###

from sys import stdin
from collections import Counter

lines = stdin.readlines()

N, K, Q = map(int, lines[0].split())
ans = [0] * N
A = Counter((int(i) - 1 for i in lines[1:]))
for k in A.keys():
    ans[k] += A[k]
print("\n".join(("Yes" if Q < K + a
                 else "No" for a in ans)))
### BUGGY CODE ###

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

####################################################
# LCS(longest common sequence)
# 部分列で最長の共通のもの
####################################################

# dp[i+1][j+1]:= s の i 文字目までと t の j 文字目まででの LCS の長さ

def main():
    S = input()
    T = input()
    ls = len(S)
    lt = len(T)

    dp = [[0]*(lt+1) for _ in range(ls+1)]
    for i in range(ls):
        for j in range(lt):
            if S[i]==T[j]:
                dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+1)
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j])
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1])
#    print(dp)
#    print(dp[ls][lt])

    # 復元
    res = ''
    i, j = ls, lt
    while (i > 0 and j > 0):
        # (i-1, j) -> (i, j) と更新されていた場合
        if dp[i][j] == dp[i-1][j]:
            i-=1   # DP の遷移を遡る

        # (i, j-1) -> (i, j) と更新されていた場合
        elif dp[i][j] == dp[i][j-1]:
            j-=1   # DP の遷移を遡る

        # (i-1, j-1) -> (i, j) と更新されていた場合
        else:
            res = S[i-1] + res
            # このとき s[i-1] == t[j-1] なので、t[j-1] + res でも OK
            i-=1
            j-=1   # DP の遷移を遡る
    print(res)

if __name__ == '__main__':
    main()

### FIXED CODE ###

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

####################################################
# LCS(longest common sequence)
# 部分列で最長の共通のもの
####################################################

# dp[i+1][j+1]:= s の i 文字目までと t の j 文字目まででの LCS の長さ

import numpy as np

def main():
    S = np.array(list(input()), dtype='unicode')
    T = np.array(list(input()), dtype='unicode')
    ls = len(S)
    lt = len(T)

    equal = S[:, None] == T[None,:]
#    print(eq)

    dp = np.zeros((ls + 1, lt + 1), dtype=int)

    for i in range(ls):
        dp[i + 1][1:] = np.maximum(dp[i][1:], dp[i][:-1] + equal[i])
        dp[i + 1] = np.maximum.accumulate(dp[i + 1])

#    for i in range(ls):
#        for j in range(lt):
#            dp[i+1][j+1] = max(dp[i][j+1], dp[i][j]+ eq[i][j])
#            dp[i+1][j+1] = max(dp[i+1][j+1] , dp[i+1][j])

#    print(dp)

    # 復元
    res = ''
    i, j = ls, lt
    while (i > 0 and j > 0):
        # (i-1, j) -> (i, j) と更新されていた場合
        if dp[i][j] == dp[i-1][j]:
            i-=1   # DP の遷移を遡る
        # (i, j-1) -> (i, j) と更新されていた場合
        elif dp[i][j] == dp[i][j-1]:
            j-=1   # DP の遷移を遡る
        # (i-1, j-1) -> (i, j) と更新されていた場合
        else:
            res = S[i-1] + res
            # このとき s[i-1] == t[j-1] なので、t[j-1] + res でも OK
            i-=1
            j-=1   # DP の遷移を遡る
    print(res)

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

from operator import mul
from functools import reduce
from bisect import*
def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

n,*a=map(int,open(0).read().split())
a.sort()
b=a.pop()
#print(a)
if n>10:
    x=bisect_left(a,b//2)
    if x>=n-1:
        print(b,a.pop())
    else:
        z=[cmb(b,a[i])for i in range(x-2,x+1)]
        y=max(z)
        print(b,a[x+z.index(y)-1])
elif n==2:
    print(b,*a)
else:
    z=[cmb(b,a[i])for i in range(n-1)]
    y=a[z.index(max(z))]
    print(b,y)


### FIXED CODE ###

n,*a=map(int,open(0).read().split())
a.sort()
b=a.pop()
dif=float("inf")
ans=0
for i in range(n-1):
    if abs(a[i]-b/2)<dif:
        ans=a[i]
        dif=abs(a[i]-b/2)
print(b,ans)
### BUGGY CODE ###

from functools import lru_cache
import sys
sys.setrecursionlimit(200000)

H,N = map(int, input().split()) #H<=10**4,N<=10**3

AB_dict = dict() #A:Atack power, B:Consumption MP

for i in range(N): #N<=10**3
    A,B = map(int, input().split())
    if A not in AB_dict:
        AB_dict[A] = B
    else:
        if B < AB_dict[A]: #同じ攻撃力なら消費MPが少ない方を優先する
            AB_dict[A] = B

@lru_cache(maxsize=None)
def get_consumption_MP(HP): #HPを削るのに必要なMPを求める関数
    ans = 10**9 + 7
    
    for AB in AB_dict.items():
        A = AB[0]
        B = AB[1]
        
        if A >= HP:
            if B < ans:
                ans = B
        else:
            if B + get_consumption_MP(HP-A) < ans:
                ans = B + get_consumption_MP(HP-A)
                
    return ans
        
print(get_consumption_MP(H))

### FIXED CODE ###


#150E
from functools import lru_cache
import sys
sys.setrecursionlimit(200000)

H,N = map(int, input().split()) #H<=10**4,N<=10**3

AB_dict = dict() #A:Atack power, B:Consumption MP

for i in range(N): #N<=10**3
    A,B = map(int, input().split())
    if A not in AB_dict:
        AB_dict[A] = B
    else:
        if B < AB_dict[A]: #同じ攻撃力なら消費MPが少ない方を優先する
            AB_dict[A] = B

@lru_cache(maxsize=None)
def get_consumption_MP(HP): #HPを削るのに必要なMPを求める関数
    ans = 10**9 + 7
    
    for AB in AB_dict.items():
        A = AB[0]
        B = AB[1]
        
        if A >= HP:
            if B < ans:
                ans = B
        else:
            if B + get_consumption_MP(HP-A) < ans:
                ans = B + get_consumption_MP(HP-A)
                
    return ans
        
print(get_consumption_MP(H))
### BUGGY CODE ###

import collections

def main():
    n =int( input())
    sn = []

    for _ in range(n):
        inWord = str(input())
        addFlag = True
        for s in sn:
            if s["word"] == inWord and len(sn) !=0:
                s["count"]+=1
                addFlag = False
                break
        if addFlag ==True:
            sn.append( {"word":inWord,"count":1})
    
    sn.sort(reverse=True,key=lambda x:x['count'])
    
    most = int(sn[0]["count"])
    mostWords=[]
    for elm in sn:
        if elm["count"] == most:
            mostWords.append(elm["word"])
        else:
            break

    mostWords.sort()

    for elm in mostWords:
        print(elm)
    return
main()



### FIXED CODE ###

def main():
    n =int( input())

    cnt=dict()
    
    for _ in range(n):
        s=input()
        if s in cnt:
            cnt[s]+=1
        else :
            cnt[s]=1
    #print(cnt)
    
    num = 0
    res =[]
    for key,value in cnt.items():
        #print(key,":::",value)
        if value > num:
            num=value
            res=[]
            res.append(key)

        elif value==num:
            res.append(key)

    #print("res::",res)

    
    #a = [k for k, v in cnt.items() if v == max(cnt.values())]


    #print("結果発表：：：：",len(res))
    res.sort()
    for elm in res:
        print(elm)


main()
### BUGGY CODE ###

from collections import Counter

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

s = Counter(c)
t = list(s.items())

nag = len(t)
x = 0
ans = 0

for i in range(nag):
    x += (t[i][1]*(t[i][1]-1))//2
    
for j in range(n):
    for k in range(nag):
        if c[j] == t[k][0]:
            ans = x - (t[k][1]-1)
            print(ans)
            break

### FIXED CODE ###

from collections import Counter

n = int(input())
c = list(map(int,input().split()))
s = Counter(c)
t = list(s.items())
nag = len(t)
x = 0
ans = 0

for i in range(nag):
    x += (t[i][1]*(t[i][1]-1))//2
    
for j in range(n):
    ans = x - s[c[j]] + 1 
    print(ans)
### BUGGY CODE ###

n, m, k = list(map(int, input().split()))
ns = list(map(int, input().split()))
ms = list(map(int, input().split()))

nss = [0]
for i, v in enumerate(ns): nss.append(nss[i] + ns[i])
mss = [0]
for i, v in enumerate(ms): mss.append(mss[i] + ms[i])

mx = 0
for i in range(n + 1):
    if nss[i] > k:
        break

    j = -1
    for v in mss:
        if nss[i] + v > k:
            break
        j += 1
    mx = max(mx, i + j)

print(mx)


### FIXED CODE ###

n, m, k = list(map(int, input().split()))
ns = list(map(int, input().split()))
ms = list(map(int, input().split()))

nss = [0]
for i, v in enumerate(ns):
    nss.append(nss[i] + ns[i])

mss = [0]
for i, v in enumerate(ms):
    mss.append(mss[i] + ms[i])

mx = 0
j = m
for i in range(n + 1):
    if nss[i] > k:
        break

    while mss[j] > k - nss[i]:
        j -= 1
    
    mx = max(mx, i + j)

print(mx)
### BUGGY CODE ###

import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    from collections import deque

    h, w = input_int_list()
    grid = []
    grid.append(["@"] * (w + 2))
    for _ in range(h):
        grid.append(["@"] + list(input()) + ["@"])
    grid.append(["@"] * (w + 2))

    # 幅優先探索で すべてを"#"に変える。
    # かかった手数分が答え
    direction = ((0, 1), (1, 0), (-1, 0), (0, -1))
    dq = deque()
    visited = set()
    # すべての"#"をdequeに入れる
    for i in range(1, h + 1):
        for j in range(1, w + 1):
            if grid[i][j] == "#":
                dq.append((i, j, 0))
                visited.add((i, j))
    ans = 0
    # 幅優先探索
    while dq:
        i, j, d = dq.popleft()
        for di, dj in direction:
            if grid[i + di][j + dj] == "." and (i + di, j + dj) not in visited:
                dq.append((i + di, j + dj, d + 1))
                visited.add((i + di, j + dj))
                ans = max(ans, d + 1)

    print(ans)
    return


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    from collections import deque

    h, w = input_int_list()
    grid = []
    visited = []
    grid.append(["@"] * (w + 2))
    visited.append([True] * (w + 2))
    for _ in range(h):
        grid.append(["@"] + list(input()) + ["@"])
        visited.append([True] + [False] * w + [True])
    grid.append(["@"] * (w + 2))
    visited.append([True] * (w + 2))

    # 幅優先探索で すべてを"#"に変える。
    # かかった手数分が答え
    direction = ((0, 1), (1, 0), (-1, 0), (0, -1))
    dq = deque()
    # すべての"#"をdequeに入れる
    for i in range(1, h + 1):
        for j in range(1, w + 1):
            if grid[i][j] == "#":
                dq.append((i, j, 0))
                visited[i][j] = True
    ans = 0
    # 幅優先探索
    while dq:
        i, j, d = dq.popleft()
        for di, dj in direction:
            if grid[i + di][j + dj] == "." and not visited[i + di][j + dj]:
                dq.append((i + di, j + dj, d + 1))
                visited[i + di][j + dj] = True
                ans = max(ans, d + 1)

    print(ans)
    return


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

from heapq import *
n,m,s=map(int,input().split())
c=[0]*n
d=[0]*n
g=[[]for i in range(n)]

for i in range(m):
    u,v,a,b=map(int,input().split())
    u-=1
    v-=1
    g[u].append((v,a,b))
    g[v].append((u,a,b))
for i in range(n):
    c[i],d[i]=map(int,input().split())

flag=0 #if this == (1<<n)-1 then finish roop
mintimes=[10**15]*n

hp=[(0,s,0)]#(time,silver,node)
while flag!=((1<<n)-1):
    time,silver,node = heappop(hp)
    flag=flag|(1<<node)
    mintimes[node]=min(mintimes[node],time)
    for atnode,costmoney,costtime in g[node]:
        if costmoney<=silver:
            heappush(hp,(time+costtime,silver-costmoney,atnode))
    if silver!=2500:
        heappush(hp,(time+d[node],silver+c[node],node))
        
print(*mintimes[1:],sep="\n")

### FIXED CODE ###

from heapq import *
n,m,s=map(int,input().split())
c=[0]*n
d=[0]*n
g=[[]for i in range(n)]

for i in range(m):
    u,v,a,b=map(int,input().split())
    u-=1
    v-=1
    g[u].append((v,a,b))
    g[v].append((u,a,b))
for i in range(n):
    c[i],d[i]=map(int,input().split())

flag=0 #if this == (1<<n)-1 then finish roop
lasttime=[[10**15]*2501 for i in range(n)]
lasttime[0][min(2500,s)]=0
mintimes=[10**15]*n
hp=[(0,min(2500,s),0)]#(time,silver,node)

while flag!=((1<<n)-1):
    time,silver,node = heappop(hp)
    flag=flag|(1<<node)
    mintimes[node]=min(mintimes[node],time)

    for atnode,costmoney,costtime in g[node]:
        nexttime,nextsilver=time+costtime,silver-costmoney
        if costmoney<=silver and lasttime[atnode][nextsilver]>nexttime:
            heappush(hp,(nexttime,nextsilver,atnode))
            lasttime[atnode][nextsilver]=min(lasttime[atnode][nextsilver],nexttime)

    nexttime,nextsilver=time+d[node],min(silver+c[node],2500)
    if silver!=2500 and lasttime[node][nextsilver]>nexttime:
        heappush(hp,(nexttime,min(silver+c[node],2500),node))
        lasttime[node][nextsilver]=min(lasttime[node][nextsilver],nexttime)
        
print(*mintimes[1:],sep="\n")
### BUGGY CODE ###

from heapq import heappush, heappop

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

min_index = [n for n, v in enumerate(s) if v == min(s)]

ans_list = [min(s)]
queue = []
i = 2

while len(ans_list) < K:
    # 候補の生成
    for m in min_index:
        for i in range(1, 6):
            if m + i < len(s):
                heappush(queue, s[m:m+i])
    while queue:
        c = heappop(queue)
        if c not in ans_list:
            ans_list.append(c)

print(ans_list[K-1])


### FIXED CODE ###

from heapq import heappush, heappop

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

min_s = sorted(list(set(s)))

res = [min(s)]
q = []
x = 0

while len(set(q)) < K:
    min_index = [n for n, v in enumerate(s) if v == min_s[x]]
    for m in min_index:
        for i in range(1, 6):
            if m+i <= len(s):
                q.append(s[m:m+i])
    x += 1

ans = sorted(list(set(q)))[K-1]

print(ans)