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

import sys
from fractions import gcd
import math
import collections
def input():
    return sys.stdin.readline()[:-1]
def prime_factor(n):
    ass = []
    for i in range(2,int(n**0.5)+1):
        while n % i==0:
            ass.append(i)
            n = n//i
    if n != 1:
        ass.append(n)
    return ass


def main():
    n=int(input())
    a=list(map(int,input().split()))
    mod=10**9+7
    # li=[0]*(max(a)+1)
    dic={}
    for i in range(n):
        tmp=collections.Counter(prime_factor(a[i]))
        # print(tmp)
        for j in list(tmp.keys()):
            if not j in dic:
                dic[j]=tmp[j]
            else:
                dic[j]=max(dic[j],tmp[j])
    ans=1
    # print(dic)
    for i in dic.keys():
        # print(dic[i],i)
        ans*=i**dic[i]
    # print(ans)
    cnt=0
    for i in range(n):
        cnt+=ans//a[i]
        cnt%=mod
    print(cnt)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from collections import deque
import heapq
import math
import bisect
from itertools import permutations
from itertools import accumulate
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7

dic={}
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# print(factorization(12))
for i in range(n):
    tmp=factorization(a[i])
    for j in range(len(tmp)):
        if not tmp[j][0] in dic:
            dic[tmp[j][0]]=tmp[j][1]
        else:
            dic[tmp[j][0]]=max(dic[tmp[j][0]],tmp[j][1])
l=1
for i in dic.keys():
    l*=i**dic[i]
    l%=mod
# print(l)
ans=0
for i in range(n):
    ans+=l*pow(a[i],mod-2,mod)
    ans%=mod
print(ans)
### BUGGY CODE ###

N,M=map(int,input().split())
A=list((map(int,input().split())))
 
m=[[1,2],[2,5],[3,5],[4,4],[5,5],[6,6],[7,3],[8,7],[9,6]]
B=[]
 
for a in A:
    B.append(m[a-1])
    
maxlist=[0]*(N+10)
 
for i in range(N+1):
    if i!=0 and maxlist[i]==0:
        continue
    else:
        for b in B:
            ans=int(str(maxlist[i])+str(b[0]))
            if ans > maxlist[i+b[1]]:
                maxlist[i+b[1]] = ans
 
print(maxlist[N])

### FIXED CODE ###

N,M=map(int,input().split())
A=list((map(int,input().split())))
 
m=[[1,2],[2,5],[3,5],[4,4],[5,5],[6,6],[7,3],[8,7],[9,6]]
B=[]
    
for a in A:
    B.append(m[a-1])

if [5,5] in B:
    if [2,5] in B:
        B.remove([2,5])
    if [3,5] in B:    
        B.remove([3,5])

if [3,5] in B and [2,5] in B:
    B.remove([2,5])

if [7,3] in B:
    if [6,6] in B:
        B.remove([6,6])
    if [9,6] in B:
        B.remove([9,6])
    
if [9,6] in B and [6,6] in B:
    B.remove([6,6])

if [1,2] in B and [7,3] in B:
    if [2,5] in B:
        B.remove([2,5])
    if [3,5] in B:
        B.remove([3,5])
    if [5,5] in B:
        B.remove([5,5])
    if [8,7] in B:
        B.remove([8,7])

if [1,2] in B and ([2,5] in B or [3,5] in B or [5,5] in B) and [8,7] in B:
    B.remove([8,7])
    
if [4,4] in B and [7,3] in B and [8,7] in B:
    B.remove([8,7])
    
if [1,2] in B and [4,4] in B:
    B.remove([4,4])

maxlist=[""]*(N+1)
 
for i in range(N+1):
    if i!=0 and maxlist[i]=="":
        continue
    else:
        for b in B:
            if i+b[1]>N:
                continue
            ans=maxlist[i]+str(b[0])
            _max=maxlist[i+b[1]]
            if len(ans)<len(_max):
                continue
            elif len(ans)>len(_max):
                maxlist[i+b[1]] = ans
            else:
                for j in range(len(ans)):
                    if ans[j]<_max[j]:
                        break
                    if ans[j]>_max[j]:
                        maxlist[i+b[1]] = ans
                        break
 
print(maxlist[N])
### BUGGY CODE ###

import sys
n, m = [int(i) for i in sys.stdin.readline().split()]
graph = {i : [] for i in range(n)}
edge_ls = []
for i in range(m):
    a, b, c = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a].append((b, c))
    edge_ls.append((a, b, c))

INF = float("inf")
d = [-INF for i in range(n)]
d[0] = 0
res = True
before_ls = [i for i in range(n)]
for i in range(n):
    flg = False
    for _from, _to, cost in edge_ls:
        if d[_to] < d[_from] + cost and d[_from] != -INF:
            d[_to] = d[_from] + cost
            before_ls[_to] = _from
            flg = True
    if not flg:
        break
cur = n - 1
root = []
while cur != 0:
    root.append(cur)
    cur = before_ls[cur]
root.append(0)
flg = False
for _from, _to, cost in edge_ls:
    if d[_to] < d[_from] + cost and d[_from] != -INF:
        d[_to] = d[_from] + cost
        before_ls[_from] = _to
        if _to in root:
            flg = True
if flg:
    print("inf")
else:
    print(d[-1])

### FIXED CODE ###

N, M = [int(i) for i in input().split()]
G_ls = []
d = [-float("inf") for i in range(N)]
for i in range(M):
    a, b, c = [int(i) for i in input().split()]
    a -= 1
    b -= 1
    G_ls.append([a,b,c])

def update(x, y, is_updated):
    if x < y:
        is_updated = True
        x = y
    return x, is_updated
d[0] = 0
G_ls.sort(key=lambda x:x[0])
for i in range(N):
    for j in range(M):
        is_updated = False
        a, b, c = G_ls[j]
        d[b], is_updated = update(d[b], d[a] + c, is_updated)
if is_updated:
    print("inf")
else:
    print(d[-1])
### BUGGY CODE ###

N, M = list(map(int, input().split()))
As = list(map(int, input().split()))
cards = {}
for i in range(N):
    cards[As[i]] = cards.get(As[i], 0) + 1

for i in range(M):
    b, c = list(map(int, input().split()))
    cnt = 0
    for k in sorted(filter(lambda x: x < c, cards.keys())):
        for _ in range(cards.get(k,0)):
            cards[k] = cards[k] - 1
            if cards[k] == 0:
                del(cards[k])
            cards[c] = cards.get(c, 0) + 1
            cnt += 1
            # print('aaa:   ', b, c, cnt)
            if cnt >= b:
                break
        if cnt >= b:
            break
    # print()
    # print(cards)
    # print()

# print(list(cards.items()))
print(sum([k * cnt for k,cnt in cards.items()]))




### FIXED CODE ###

N, M  = map(int,input().split())
As = sorted(list(map(int,input().split())))
di = {}
for i in range(M):
    b, c = map(int,input().split())
    di[c] = di.get(c, 0) + b

keys = list(sorted(di.keys(), reverse=True))
ichi = 0
for i in range(N):
    try:
        if keys[ichi] > As[i]:
            As[i] = keys[ichi]
            di[keys[ichi]] -= 1
        else:
            break
        if di[keys[ichi]] == 0:
            ichi += 1
    except:
        pass
print(sum(As))
### BUGGY CODE ###

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

for a in A:
  prod *= a

if prod > 10**18:
  prod = -1

print(prod) 

### FIXED CODE ###

def main():
  N = int(input())
  A = list(map(int, input().split()))
  prod = 1

  for a in A:
    if a == 0:
      print(0)
      return

  for a in A:
    prod *= a
    if prod > 1000000000000000000:
      print(-1)
      return

  print(prod) 

main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline


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

    for i in range(n):
        s = s ^ {int(input())}

    print(len(s))


main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

import bisect

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

    for i in range(n):
        a = int(input())
        i = bisect.bisect_left(s, a)
        if len(s) > i and s[i] == a:
            s.remove(a)
        else:
            s.insert(i, a)


    print(len(s))


main()
### BUGGY CODE ###

import sys
# sys.setrecursionlimit(100000)
from collections import deque


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():
    n = input_int()
    d = dict()
    for i in range(1, n + 1):
        d[i] = deque(input_int_list())
    day = 0
    matches = 0
    while True:
        played = set()
        for a, v in d.items():
            if d[a] and a not in played:
                b = d[a][0]
                if d[b] and a == d[b][0] and b not in played:
                    d[a].popleft()
                    d[b].popleft()
                    played.add(a)
                    played.add(b)
                    matches += 1
        if not played:
            break
        day += 1

    if matches == (n * (n - 1)) // 2:
        print(day)
    else:
        print(-1)


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():
    n = input_int()
    d = dict()
    for i in range(1, n + 1):
        d[i] = input_int_list()[::-1]
    day = 0
    candi = set(range(1, n + 1))
    rest = (n * (n - 1)) // 2
    while rest:
        played = set()
        for a in candi:
            if d[a] and d[d[a][-1]][-1] and a == d[d[a][-1]][-1]:
                played.add(a)
                played.add(d[a][-1])

        if not played:
            break

        candi.clear()

        rest -= len(played) // 2
        for a in played:
            candi.add(a)
            d[a].pop()
            if d[a]:
                candi.add(d[a][-1])
        day += 1

    if rest == 0:
        print(day)
    else:
        print(-1)


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

N=int(input())
number=list(map(int,input().split()))
SUM=sum(number)
number_sum=[0]*(N-1)

for i in range(N-1):
  number_sum[i]=abs(sum(number[:i+1])*2-SUM)

print(min(number_sum))

### FIXED CODE ###

N=int(input())
number=list(map(int,input().split()))
Sum=sum(number)
number_sum=[0]*N
number_sum[0]=number[0]
result=[0]*(N-1)
for i in range(1,N):
  number_sum[i]=number_sum[i-1]+number[i]
result[0]=abs(number_sum[0]*2-Sum)
for i in range(1,N-1):
  result[i]=abs(((number_sum[i])*2-Sum))

print(min(result))
### BUGGY CODE ###

x = int(input())
a=0
b=0
y=0
yy = 0
z=0
m=0

while True:
    if x == 0:
        break
    for a in range(1,10**9,1):
        y=a**5
        yy=(a+1)**5
        z=x-y
        z*=-1
        if z == 0:
            b = 0
            break
        if z < 0 and x<yy:
            for b in range(-1,-10**9,-1):
                m=z-b**5
                if z-b**5 == 0:
                    break
            else:
                continue
            break
        elif z > 0 and x<yy:
            for b in range(1,10**9,1):
                if z-b**5 == 0:
                    break
            else:
                continue
            break
    else:
        continue
    break

print(str(a)+' '+str(b))

### FIXED CODE ###

x = int(input())
a=0
b=0

for a in range(-118,119,1):
    for b in range(-119,118,1):
        if a**5-b**5 == x:
            break

    else:
        continue
    break

print(str(a)+' '+str(b))
### BUGGY CODE ###

s=input()
n=len(s)
List=[0]*2019
ans=0
for i in range(0,n):
  List[(int(s[i:])%2019)]+=1
  #print(s[i:],int(s[i:])%2019)
  
#print(List)
ans=List[0]
for i in range(2019):
  ans+=(List[i]*(List[i]-1))//2
  
print(ans)

### FIXED CODE ###

S=input()[::-1]
List=[0]*2019
ans=0
a=1
d=0

for s in S:
  d=d+int(s)*a
  List[d%2019]+=1
  a=a*10
  a=a%2019
  #print(s[i:],int(s[i:])%2019)
  
#print(List)
ans=List[0]
for i in List:
  if (i>=2):
    ans+=(i*(i-1))//2
  
print(ans)
### BUGGY CODE ###

#129_C
n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
dp=[1 for i in range(n+1)]
for i in range(1,n+1):
    if i in a:
        dp[i]=0
    elif i==1:
        dp[i]=dp[i-1]
    else:
        dp[i]=dp[i-1]+dp[i-2]
        
print(dp[n]%(10**9+7))

### FIXED CODE ###

#129_C
n,m=map(int,input().split())
a={int(input()) for _ in range(m)}
mod=10**9+7
dp=[0 for i in range(n+1)]
dp[0]=1
for i in range(1,n+1):
    if i in a:
        dp[i]=0
    else:
        dp[i]=(dp[i-1]+dp[i-2])%mod
        
print(dp[n])
### BUGGY CODE ###

import sys
N=int(sys.stdin.readline())
L=list(map(int,sys.stdin.readline().split()))
count=[0]*N
for K in range(N):
  B = L[0:K]+L[K+1:] #popを使うとなぜか元のAまで変化してしまう
  C=list(set(L[0:K]+L[K+1:]))
  d = [0]*len(C)
  x=0
  for i in range(len(C)):
    d[i] = int((B.count(C[i]))*(B.count(C[i])-1)/2)
    x += d[i]
  print(x)


### FIXED CODE ###

import sys
from collections import Counter
N=int(sys.stdin.readline())
L=list(map(int,sys.stdin.readline().split()))
C=Counter(L)
x=0
for a in C.values():
  x += int(a*(a-1)/2)  
for K in range(N):
  print(x-C[L[K]]+1)
### BUGGY CODE ###

n,w=list(map(int, input().split()))
wv=[list(map(int, input().split())) for _ in range(n)]

dp = [[0 for _ in range(w+1)] for _ in range(n+1)]
dp[0][0] = 0

for i in range(n):
    for j in range(w+1):
        if j >= wv[i][0]:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - wv[i][0]] + wv[i][1])
        else:
            dp[i+1][j] = dp[i][j]

print(dp[-1][-1])


### FIXED CODE ###

n,w = list(map(int, input().split()))
wv = [list(map(int, input().split())) for _ in range(n)]

v = sum(list(map(lambda x: x[1], wv)))
dp = [[float("inf")]*(v+1) for _ in range(n+1)]
dp[0][0] = 0

for i in range(n):
    a = wv[i]
    for j in range(v+1):
        if a[1] <= j:
            dp[i+1][j] = min(dp[i][j], dp[i][j- a[1]] + a[0])
        else:
            dp[i+1][j] = dp[i][j]

dpl = dp[-1]
for i in range(v, -1, -1):
    if dpl[i] <= w:
        print(i)
        break
### BUGGY CODE ###

S = input()
Q = int(input())
s = S

rev = 0
front = ''
back = ''

for i in range(Q):
    query = input()
    ti = list(query)[0]
    if ti == '1':
        rev = (rev + 1) % 2
    else:
        ti, fi, ci = query.split()
        if (int(fi) + rev) == 2:
            back += ci
        else:
            front = ci + front

s = front + s + back

if rev == 1:
    s = list(s)
    s.reverse()
    s = ''.join(s)
print(s)

### FIXED CODE ###

class Node:
    def __init__(self, char: str):
        self.before = None
        self.char = char
        self.next = None

class Linked_List:
    def __init__(self):
        self.head = None
        self.tail = None
    
    def add_head(self, node):
        if self.head is None:
            self.head = node
            self.tail = node
        else:
            node.next = self.head
            self.head.before = node
            self.head = node

    def add_tail(self, node):
        if self.tail is None:
            self.head = node
            self.tail = node
        else:
            node.before = self.tail
            self.tail.next = node
            self.tail = node

    def show(self, is_reversed: bool):
        ret = []
        node = self.tail if is_reversed else self.head
        while not node is None:
            c = ''.join(list(node.char)[::-1]) if is_reversed else node.char
            ret.append(c)
            node = node.before if is_reversed else node.next
        print(''.join(ret))

S = input()
Q = int(input())
ll = Linked_List()
ll.add_head(Node(S))
is_reversed = False

for _ in range(Q):
    query = input()
    if query[0] == '1':
        is_reversed = False if is_reversed else True
    else:
        t, f, c = query.split()
        if is_reversed:
            c = ''.join(list(c)[::-1])
        if f == '1':
            if is_reversed:
                ll.add_tail(Node(c))
            else:
                ll.add_head(Node(c))
        else:
            if is_reversed:
                ll.add_head(Node(c))
            else:
                ll.add_tail(Node(c))

ll.show(is_reversed)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
INF = 10**9

def calc(N, A):
    ans = 0
    for i in range(N-1):
        for j in range(i+1, N):
            ans += A[i] ^ A[j]

    ans = ans % (INF + 7)
    return ans

print(calc(N, A))

### FIXED CODE ###

import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
ans = 0
mod = 10 ** 9 + 7

for i in range(60):
    x, y = 0, 0    
    B = A >> i & 1
    x = np.count_nonzero(B)
#     for Ai in A:
#         if Ai >> i & 1:
#             x += 1
    y = N - x
    ans += (x * y) * (2 ** i)
    
print(ans%mod)
### BUGGY CODE ###

import collections
import sys
input=sys.stdin.readline

def calc():
  h,w,k=map(int,input().split())
  sy,sx,gy,gx=map(int,input().split())
  sy,sx,gy,gx=sy-1,sx-1,gy-1,gx-1
  board=[input() for _ in range(h)]
  q=collections.deque()
  q.append((sx,sy))
  checked=[[[0,0,0,0] for _ in range(w)] for _ in range(h)]
  checked[sy][sx][0]=1
  checked[sy][sx][1]=1
  checked[sy][sx][2]=1
  checked[sy][sx][3]=1
  cost=[[10**18]*w for _ in range(h)]
  cost[sy][sx]=0
  while len(q)!=0:
    x,y=q.popleft()
    c=cost[y][x]
    for i in range(1,k+1):
      if x+i<w and checked[y][x+i][0]==0 and board[y][x+i]=='.' and c<cost[y][x+i]:
        checked[y][x+i][0]=1
        cost[y][x+i]=c+1
        q.append((x+i,y))
      else:
        break
    for i in range(1,k+1):
      if x-i>=0 and checked[y][x-i][1]==0 and board[y][x-i]=='.' and c<cost[y][x-i]:
        checked[y][x-i][1]=1
        cost[y][x-i]=c+1
        q.append((x-i,y))
      else:
        break
    for i in range(1,k+1):
      if y+i<h and checked[y+i][x][2]==0 and board[y+i][x]=='.' and c<cost[y+i][x]:
        checked[y+i][x][2]=1
        cost[y+i][x]=c+1
        q.append((x,y+i))
      else:
        break
    for i in range(1,k+1):
      if y-i>=0 and checked[y-i][x][3]==0 and board[y-i][x]=='.' and c<cost[y-i][x]:
        checked[y-i][x][3]=1
        cost[y-i][x]=c+1
        q.append((x,y-i))
      else:
        break
  if cost[gy][gx]==10**18:
    print(-1)
  else:
    print(cost[gy][gx])
calc()

### FIXED CODE ###

import collections

h,w,k=map(int,input().split())
sy,sx,gy,gx=map(int,input().split())
sy,sx,gy,gx=sy-1,sx-1,gy-1,gx-1
board=[input() for _ in range(h)]
q=collections.deque()
q.append((sx,sy))
checked=[[0]*w for _ in range(h)]
checked[sy][sx]=1
cost=[[10**18]*w for _ in range(h)]
cost[sy][sx]=0
dx=[1,0,-1,0]
dy=[0,1,0,-1]
while len(q)!=0:
  x,y=q.popleft()
  c=cost[y][x]
  for i in range(4):
    for j in range(1,k+1):
      if x+j*dx[i]<0 or w<=x+j*dx[i] or y+j*dy[i]<0 or h<=y+j*dy[i]:
        break
      if board[y+j*dy[i]][x+j*dx[i]]=='@':
        break
      if cost[y+j*dy[i]][x+j*dx[i]]<=c:
        break
      if cost[y+j*dy[i]][x+j*dx[i]]>c+1:
        q.append((x+j*dx[i],y+j*dy[i]))
        cost[y+j*dy[i]][x+j*dx[i]]=c+1
if cost[gy][gx]==10**18:
  print(-1)
else:
  print(cost[gy][gx])
### BUGGY CODE ###

A=list(map(int,input().split()))
t=True
sum=2019
if t:
    for i in range(int(A[1])):
        if i>=A[0]:
            for t in range (int(A[1])+1):
                if t>i:
                    if i*t%2019<=sum:
                        sum=i*t%2019
print(sum)

### FIXED CODE ###

l,r=list(map(int,input().split()))
f=True
C=2019
if (r-l)<2019:
    for i in range(l,r+1):
        if C==0:
            break
        for t in range(i+1,r+1):
            if t*i%2019<C:
                C=t*i%2019
                if C==0:
                    break
else:
    C=0
print(C)
### BUGGY CODE ###

n,m = map(int,input().split())
li = list(map(int,input().split()))	
for i in range(m):
  li.sort()
  li[-1] = li[-1]//2
print(sum(li))

### FIXED CODE ###

import heapq

n,m = map(int,input().split())
a = list(map(int,input().split()))
a = [-x for x in a]
heapq.heapify(a) 
ans =0
for i in range(m):
  b = a[0]
  c = (-1)*b //2
  heapq.heappop(a) 
  heapq.heappush(a, c*(-1)) 
print(sum(a)*(-1))
### BUGGY CODE ###

n = int(input())
c = input().split()
c = [int(n) for n in c]

for i in range(1, n+1):
    print(c.count(i))


### FIXED CODE ###

n = int(input())
c = input().split()
c = [int(n) for n in c]

s = dict.fromkeys([int(n) for n in range(1,n+1)], 0)

for i in c:
    s[i] = s[i] + 1

for i in range(1, n+1):
    print(s[i])
### BUGGY CODE ###

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

a = []
for i in range(m):
    a.append(int(input()))

dp = []
for dpi in range(n):
    dp.append(0)

for j in range(n):
    if j == 0 and j+1 not in a:
        dp[j] = 1
    elif j == 1 and j+1 not in a:
        dp[j] = dp[j-1] + 1
    elif j > 1 and j+1 not in a:
        dp[j] = dp[j-1] + dp[j-2]

print(dp[n-1] % 1000000007)

### FIXED CODE ###

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

a = []
for i in range(m):
    a.append(int(input()))

dp = []
for dpi in range(n):
    dp.append(0)

k = 0
a.append(0)
for j in range(n):
    if j+1 == a[k]:
        k += 1
        continue
    if j == 0:
        dp[j] = 1
    elif j == 1:
        dp[j] = dp[j-1] + 1
    elif j > 1:
        dp[j] = dp[j-1] + dp[j-2]

print(dp[n-1] % 1000000007)
### BUGGY CODE ###

a = int(input())
l = list(map(int, input().split()))
tot = 0
for i in range(a):
    if tot <= a - 1:
        print(l.count(i + 1))
        tot += l.count(i + 1)
    else:
        n = a - (i + 1)
        print('0\n' * n)
        exit()


### FIXED CODE ###

import collections
a = int(input())
l = list(map(int, input().split()))
l_2 = collections.Counter(l)
for i in range(a):
    print(l_2[i + 1])
### BUGGY CODE ###

N = int(input())
P = list(map(int, input().split()))
ans = 0
for i in range(N):
    for j in range(0, i):
        if P[j] < P[i]:
            break
    else:
        ans += 1
print(ans)


### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))
ans = 1
dp = [0 for i in range(N + 1)]
dp[0] = P[0] # min
for i in range(N - 1):
    if P[i + 1] <= dp[i]:
        ans += 1
        dp[i + 1] = P[i + 1]
    else:
        dp[i + 1] = dp[i]

print(ans)
### BUGGY CODE ###

s = input()
k = int(input())

sublist = []

for start in range(len(s)):
    for end in range(start+1, len(s) + 1):
        sublist.append(s[start:end])
list_uq = list(set(sublist))
list_sorted = sorted(list_uq)
print(list_sorted[k-1])


### FIXED CODE ###

s = input()
k = int(input())


sublist = []
for start in range(len(s)):
    end = min(start + k, len(s))
    for end in range(start+1, end + 1):
        sublist.append(s[start:end])

unique = sorted(list(set(sublist)))
print(unique[k-1])