AtCoder Beginner Contest 097 - K-th Substring

You are given a string s.
Among the different substrings of s, print the K-th lexicographically smallest one.
A substring of s is a string obtained by taking out a non-empty contiguous part in s.
For example, if s = ababc, a, bab and ababc are substrings of s, while ac, z and an empty string are not.
Also, we say that substrings are different when they are different as strings.
Let X = x_{1}x_{2}...x_{n} and Y = y_{1}y_{2}...y_{m} be two distinct strings. X is lexicographically larger than Y if and only if Y is a prefix of X or x_{j} > y_{j} where j is the smallest integer such that x_{j} \neq y_{j}.

-----Constraints-----
 - 1 ≤ |s| ≤ 5000
 - s consists of lowercase English letters.
 - 1 ≤ K ≤ 5
 - s has at least K different substrings.

-----Partial Score-----
 - 200 points will be awarded as a partial score for passing the test set satisfying |s| ≤ 50.

-----Input-----
Input is given from Standard Input in the following format:
s
K

-----Output-----
Print the K-th lexicographically smallest substring of K.

-----Sample Input-----
aba
4

-----Sample Output-----
b

s has five substrings: a, b, ab, ba and aba.
Among them, we should print the fourth smallest one, b.
Note that we do not count a twice.

Source: atcoder | Difficulty: EASY


Solutions:
s = input()
K = int(input())
case = []
append = case.append
for i in range(1, K + 1):
	for idx in range(0, len(s) - (i - 1)):
		if s[idx:idx + i] not in case:
			append(s[idx:idx + i])
case.sort(reverse=True)
print(case[-K])


s = input()
k = int(input())
n = len(s)
a = set()
for i in range(5):
	for j in range(n - i):
		a.add(s[j:j + i + 1])
a = sorted(list(a))
print(a[k - 1])


S = input()
K = int(input())
L = set()
for i in range(K):
	for j in range(len(S) - i):
		L.add(S[j:j + i + 1])
L = sorted(list(L))
print(L[K - 1])


(s, K) = (input(), int(input()))
res = set()
for i in range(K):
	for j in range(len(s) - i):
		res.add(s[j:j + i + 1])
res = sorted(list(res))
print(res[K - 1])


s = input()
k = int(input())
n = len(s)
setdic = set()
for i in range(n):
	for j in range(1, k + 1):
		setdic.add(s[i:i + j])
lians = sorted(list(setdic))
print(lians[k - 1])


s = input()
K = int(input())
S = set([])
for i in range(len(s)):
	for j in range(i + 1, i + 1 + K):
		S.add(s[i:j])
ans = sorted(S)[K - 1]
print(ans)


import bisect

def solve(S, K):
	n = len(S)
	l = [''] + ['あ'] * 5
	for i in range(n):
		for j in range(i, i + 5):
			tmp = S[i:j + 1]
			tmp_num = bisect.bisect_left(l, tmp)
			if tmp_num > 5:
				continue
			elif l[tmp_num] != tmp:
				l.insert(tmp_num, tmp)
				l.pop(-1)
	print(l[K])

def __starting_point():
	S = input()
	K = int(input())
	solve(S, K)
__starting_point()


S = input()
k = int(input())
A = set()
for l in range(k + 1):
	for i in range(len(S) - l):
		A.add(S[i:i + l + 1])
A = sorted(list(A))
print(A[k - 1])


s = input()
k = int(input())
cnt = set()
for i in range(len(s)):
	for j in range(min(len(s) - i, k)):
		cnt.add(s[i:i + j + 1])
ans = sorted(list(cnt))
print(ans[k - 1])


s = input()
K = int(input())
S = set()
for i in range(1, K + 1):
	S |= set([s[n:n + i] for n in range(0, max(len(s) - i + 1, 0))])
print(sorted(list(S))[K - 1])


s = input()
K = int(input())
moji = []
for i in range(K):
	for j in range(len(s) - i):
		moji.append(s[j:j + i + 1])
moji = list(set(moji))
moji.sort()
print(moji[K - 1])


s = input()
k = int(input())
A = set()
for i in range(len(s)):
	for j in range(k):
		if i + j <= len(s) - 1:
			A.add(s[i:i + j + 1])
B = sorted(A)
print(B[k - 1])


s = input()
print(sorted({s[i:i + j] for i in range(len(s)) for j in range(6)})[int(input())])


S = input()
N = len(S)
K = int(input())
Data = set()
for s in range(N):
	for e in range(s + 1, min(N + 1, s + 1 + K + 1)):
		Data.add(S[s:e])
print(sorted(Data)[K - 1])


s = input()
K = int(input())
d = set()
for l in range(1, K + 1):
	for i in range(len(s) + 1 - l):
		d |= {s[i:i + l]}
print(sorted(list(d))[K - 1])


s = input()
n = int(input())
t = set()
for i in range(len(s)):
	for j in range(i + 1, i + n + 1):
		t.add(s[i:j])
l = list(t)
l.sort()
print(l[n - 1])


s = input()
s = s + '0'
K = int(input())
p = set()
for i in range(len(s)):
	for j in range(1, 6):
		if i + j <= len(s) - 1:
			p.add(s[i:j + i])
p = sorted(p)
print(p[K - 1])


s = input()
K = int(input())
S = set()
for i in range(1, K + 1):
	for j in range(len(s)):
		S.add(s[j:i + j])
S = list(S)
S.sort()
print(S[K - 1])


s = str(input())
K = int(input())
l = len(s)
a = []
for i in range(0, l):
	for j in range(i, min(l, i + 5)):
		a.append(s[i:j + 1])
a = sorted(list(set(a)))
print(a[K - 1])


s = input()
k = int(input())
ans = []
for i in range(len(s)):
	for j in range(i + 1, min(k + i + 1, len(s) + 1)):
		ans.append(s[i:j])
ans = list(set(ans))
ans.sort()
print(ans[k - 1])


s = input()
k = int(input())
n = len(s)
dic = {}
ansl = []
for i in range(n):
	for j in range(i, n):
		length = j - i + 1
		if length > k:
			continue
		partial = s[i:j + 1]
		if not dic.get(partial, False):
			dic[partial] = True
			ansl.append(partial)
ansl.sort()
print(ansl[k - 1])


(s, k) = (input(), int(input()))
print(sorted(set([s[j:j + i] for i in range(1, min(6, len(s) + 1)) for j in range(len(s) - i + 1)]))[k - 1])


S = input()
N = len(S)
K = int(input())
StringList = []
for TSt in range(0, N):
	for TEd in range(TSt + 1, TSt + K + 1):
		StringList.append(S[TSt:TEd])
SetString = sorted(set(StringList))
print(SetString[K - 1])


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left, bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil, pi
from operator import itemgetter

def I():
	return int(input())

def MI():
	return map(int, input().split())

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

def LI2():
	return [int(input()) for i in range(n)]

def MXI():
	return [[LI()] for i in range(n)]

def SI():
	return input().rstrip()

def printns(x):
	print('\n'.join(x))

def printni(x):
	print('\n'.join(list(map(str, x))))
inf = 10 ** 17
mod = 10 ** 9 + 7
s = SI()
k = I()
n = len(s)
strs = []
for i in range(n):
	for j in range(1, k + 1):
		strs.append(s[i:i + j])
print(sorted(list(set(strs)))[k - 1])


s = input()
k = int(input())
l = set()
for i in range(len(s)):
	for j in range(1, k + 1):
		l.add(s[i:i + j])
ll = list(l)
ll.sort()
print(ll[k - 1])


s = input()
K = int(input())
a = set([])
for x in range(len(s)):
	for y in range(x, x + 5):
		a.add(s[x:y + 1])
print(sorted(a)[K - 1])


S = input()
K = int(input())
N = len(S)
x = set(list(S))
for i in range(K):
	for j in range(N - i):
		x.add(S[j:j + i + 1])
x = list(x)
x.sort()
print(x[K - 1])


s = input()
k = int(input())
tmp = []
for i in range(len(s)):
	for j in range(1, k + 1):
		tmp.append(s[i:i + j])
tmp = set(tmp)
tmp2 = sorted(tmp)
print(tmp2[k - 1])


s = input()
K = int(input())
N = len(s)
words = set()
for k in range(K):
	for i in range(N - k):
		words.add(s[i:i + k + 1])
print(sorted(words)[K - 1])


s = input()
m = int(input())
c = []
for i in range(len(s)):
	for k in range(1, m + 1):
		c.append(s[i:i + k])
b = sorted(list(set(c)))
print(b[m - 1])


s = input()
k = int(input())
array = []
for i in range(0, k):
	for j in range(0, len(s) - i):
		array.append(s[j:j + i + 1])
print(sorted(set(array))[k - 1])


def main():
	S = input()
	N = len(S)
	K = int(input())
	top_k = []
	for i in range(N):
		for j in range(i + 1, min([i + K, N]) + 1):
			st = S[i:j]
			top_k.append(st)
			if len(top_k) > K:
				top_k = list(set(top_k))
				top_k.sort()
				top_k = top_k[:K]
	top_k.sort()
	print(top_k[-1])

def __starting_point():
	main()
__starting_point()


import collections
s = input()
k = int(input())
b = collections.Counter(s)
c = sorted(b.items())
con = []
n = 0
while True:
	con.append(c[n][0])
	if len(con) == k:
		break
	for i in range(len(c)):
		check = c[n][0] + c[i][0]
		if check in s:
			con.append(check)
			if len(con) >= k:
				break
			for i_2 in range(len(c)):
				check_2 = check + c[i_2][0]
				if check_2 in s:
					con.append(check_2)
					if len(con) >= k:
						break
					for i_3 in range(len(c)):
						check_3 = check_2 + c[i_3][0]
						if check_3 in s:
							con.append(check_3)
							if len(con) >= k:
								break
							for i_4 in range(len(c)):
								check_4 = check_3 + c[i_4][0]
								if check_4 in s:
									con.append(check_4)
									if len(con) >= k:
										break
	if len(con) >= k:
		break
	n += 1
print(con[k - 1])


from collections import deque
s = input()
k = int(input())

def index_Multi(List, liter):
	index_L = []
	for val in range(0, len(List)):
		if liter == List[val]:
			index_L.append(val)
	return index_L

def substr(s, k, j):
	n = ord('a')
	while True:
		l = index_Multi(s, chr(n + j))
		word = []
		if len(l) == 0:
			n += 1
		else:
			for p in l:
				for i in range(k):
					word.append(s[p:p + i + 1])
			sword = set(word)
			if len(sword) >= k:
				tword = list(sword)
				tword.sort()
				return tword[k - 1]
			else:
				return substr(s, k - len(sword), j + 1)
			break
print(substr(s, k, 0))


s = input()
n = int(input())
l = set()
for i in range(len(s)):
	for j in range(i, i + n):
		l.add(s[i:j + 1])
print(sorted(list(l))[n - 1])


s = input()
k = int(input())
li = set()
for p in range(5):
	for i in range(len(s) - p):
		li.add(s[i:i + 1 + p])
li = list(li)
li.sort()
print(li[k - 1])


s = input()
k = int(input())
n = len(s)
subs = []
for i in range(n):
	for j in range(min(5, n - i)):
		subs.append(s[i:i + j + 1])
print(sorted(set(subs))[k - 1])


from itertools import combinations
s = input()
n = int(input())
le = len(s)
tmp = s[:5]
for i in range(le - 4):
	tmp = min(tmp, s[i:i + 5])
seed = tuple(combinations(list(range(min(6, le + 1))), 2))
res = set()
for (i, j) in seed:
	res.add(tmp[i:j])
ans = sorted(res)
print(ans[n - 1])


s = str(input())
K = int(input())
substrings = set([])
for i in range(5):
	for j in range(len(s) - i):
		substrings.add(s[j:j + i + 1])
print(sorted(substrings)[K - 1])


s = input()
k = int(input())
c = set()
for i in range(len(s)):
	for j in range(k):
		c.add(s[i:i + j + 1])
print(sorted(list(c))[k - 1])


s = input().strip()
k = int(input())
A = []
for i in range(len(s)):
	for j in range(1, 6):
		if i + j <= len(s):
			A.append(s[i:i + j])
B = sorted(list(set(A)))
print(B[k - 1])


s = input()
n = len(s)
k = int(input())
l = set()
for i in range(n):
	for j in range(1, 6):
		if i + j <= n:
			l.add(s[i:i + j])
l = sorted(l)
print(l[k - 1])


s = input()
k = int(input())
a = []
for i in range(len(s)):
	for j in range(1, k + 2):
		a.append(s[i:i + j])
print(sorted(set(a))[k - 1])


s = input().strip()
K = int(input())
S = set()
for i in range(len(s)):
	for w in range(1, K + 1):
		S.add(s[i:i + w])
print(sorted(S)[K - 1])


s = input()
K = int(input())
L = []
for i in range(len(s)):
	for j in range(1, K + 1):
		L.append(s[i:i + j])
print(sorted(set(L))[K - 1])


def calc(s, k, n):
	bruh = {}
	for i in range(1, k + 1):
		for j in range(n - (i - 1)):
			bruh[s[j:j + i]] = 0
	another = bruh.keys()
	another = sorted(another)
	print(another[k - 1])
s = input()
k = int(input())
n = len(s)
calc(s, k, n)


import sys
input = sys.stdin.readline
S = input().rstrip()
K = int(input())
Ans = []
for k in range(5):
	for i in range(len(S) - k):
		s = S[i:i + k + 1]
		if s not in Ans:
			Ans.append(s)
Ans.sort()
print(Ans[K - 1])


s = input()
k = int(input())
alphabets = [chr(i + 97) for i in range(26)]
for char in alphabets:
	l = []
	for i in range(len(s)):
		if s[i] == char:
			l.append(s[i:])
	if l == []:
		continue
	if k == 1:
		print(l[0][0])
		return
	k -= 1
	strings = set([])
	for i in l:
		for j in range(2, min(k + 2, len(i) + 1)):
			strings.add(i[:j])
	strings = list(strings)
	strings.sort()
	if len(strings) >= k:
		print(strings[k - 1])
		return
	else:
		k -= len(strings)


s = input()
k = int(input())
s_list = []
for i in range(len(s)):
	for j in range(k):
		s_list.append(s[i:i + j + 1])
s_list = sorted(list(set(s_list)))
print(s_list[k - 1])


(s, n) = (input(), int(input()))
ss = [s[i:i + j + 1] for i in range(len(s)) for j in range(5)]
print(sorted(set(ss), key=sorted(ss).index)[n - 1])


s = input()
K = int(input())
mojiretsu = set()
for i in range(0, len(s)):
	for k in range(1, 6):
		mojiretsu.add(s[i:i + k])
ans = sorted(mojiretsu)
print(ans[K - 1])


s = input()
k = int(input())
arr = set()
for i in range(min(k, len(s))):
	for j in range(len(s)):
		arr.add(s[j:j + i + 1])
arr = list(arr)
arr.sort()
print(arr[k - 1])


s = input()
k = int(input())
n = len(s)
ans = set()
for i in range(n):
	for j in range(i + 1, i + k + 1):
		ans.add(s[i:j])
ans = sorted(ans)
print(ans[k - 1])


S = input()
K = int(input())
S_len = len(S)
ans = set()
for i in range(0, K + 1):
	for j in range(0, S_len):
		if j + i <= S_len:
			t = S[j:j + i]
			if t != '':
				ans.add(t)
ans = list(ans)
ans.sort()
print(ans[K - 1])


s = input()
k = int(input())
l = []
for i in range(1, k + 1):
	for j in range(len(s) - i + 1):
		l.append(s[j:j + i])
l = list(set(l))
l.sort()
print(l[k - 1])


s = input()
k = int(input())
print(sorted({s[i:i + j] for i in range(len(s)) for j in range(1, k + 1)})[k - 1])


import sys
sr = lambda : sys.stdin.readline().rstrip()
ir = lambda : int(sr())
lr = lambda : list(map(int, sr().split()))
S = sr()
K = ir()
cand = set()
length = len(S)
for i in range(length):
	for j in range(1, 6):
		cand.add(S[i:i + j])
answer = sorted(list(cand))[K - 1]
print(answer)


s = input()
k = int(input())
seen = set()
i = 1
while i <= k:
	for j in range(len(s)):
		seen.add(s[j:j + i])
	i += 1
print(sorted(seen)[k - 1])


s = input()
k = int(input())
SUBSTRINGS = set()
for i in range(len(s)):
	for j in range(i + 1, i + 6):
		SUBSTRINGS.add(s[i:j])
SUBSTRINGS = sorted(SUBSTRINGS)
print(SUBSTRINGS[k - 1])


s = input()
k = int(input())
subs = set()
for ln in range(1, k + 1):
	for i in range(len(s)):
		subs.add(s[i:i + ln])
print(sorted(list(subs))[k - 1])


s = input()
K = int(input())
subs = []
for i in range(len(s)):
	for k in range(K):
		subs.append(s[i:i + 1 + k])
print(sorted(set(subs))[K - 1])


s = input()
k = int(input())
n = len(s)
temp_set = set()
for i in range(n):
	for j in range(i + 1, min(i + k + 1, n + 1)):
		temp_set.add(s[i:j])
temp_list = sorted(list(temp_set))
print(temp_list[k - 1])


s = input()
k = int(input())
subs = set()
for l in range(1, k + 1):
	for i in range(len(s) - l + 1):
		subs.add(s[i:i + l])
subs = sorted(subs)
print(subs[k - 1])


s = input()
k = int(input())
a = {s}
for i in range(k):
	for j in range(len(s) - i):
		a.add(s[j:j + i + 1])
print(sorted(list(a))[k - 1])


s = input()
k = int(input())
l = len(s)
sub = set()
for i in range(l):
	for j in range(1, k + 1):
		sub.add(s[i:i + j])
print(sorted(sub)[k - 1])


s = input()
k = int(input())
cand = []
for i in range(len(s)):
	temp = ''
	for j in range(k):
		if i + j >= len(s):
			continue
		temp += s[i + j]
		cand.append(temp)
cand.sort()
ans = cand.pop(0)
k -= 1
while k != 0:
	temp = cand.pop(0)
	if temp == ans:
		continue
	ans = temp
	k -= 1
print(ans)


s = input()
K = int(input())
subs = set()
for i in range(len(s)):
	for j in range(i + 1, i + K + 1):
		subs.add(s[i:j])
print(sorted(subs)[K - 1])


S = input()
k = int(input())
T = set()
for i in range(len(S)):
	for j in range(1, 6):
		T.add(S[i:i + j])
T = list(T)
print(sorted(T)[k - 1])


import sys
read = sys.stdin.read
readlines = sys.stdin.readlines

def main():
	s = list(input())
	k = int(input())
	subs = set()
	lens = len(s)
	for i1 in range(k + 1):
		for i2 in range(lens - i1):
			subs.add(''.join(s[i2:i2 + i1 + 1]))
	subs_l = list(subs)
	subs_l.sort()
	print(subs_l[k - 1])

def __starting_point():
	main()
__starting_point()


import sys
s = input()
K = int(input())
a_list = sorted(set(s))
for i in a_list:
	if K == 1:
		print(i)
		return
	p = []
	for (j, x) in enumerate(s):
		if x == i:
			p.append(s[j:min(j + K, len(s))])
	p.sort()
	t = K
	for j in range(len(p)):
		if j != len(p) - 1:
			if p[j] == p[j + 1][0:len(p[j])]:
				continue
		if len(p[j]) < t:
			t -= len(p[j]) - 1
		else:
			print(p[j][0:t])
			return
	K = t - 1


s = input()
k = int(input())
l = []
for i in range(len(s)):
	for j in range(i + 1, min(i + k + 1, len(s) + 1)):
		l.append(s[i:j])
print(sorted(list(set(l)))[k - 1])


s = input()
K = int(input())
sub = []
for i in range(len(s)):
	for j in range(i, min(i + K, len(s))):
		sub.append(s[i:j + 1])
sub = sorted(set(sub))
print(sub[K - 1])


s = input()
K = int(input())
ss = [s[i:i + j + 1] for i in range(len(s)) for j in range(K)]
print(sorted(set(ss))[K - 1])


S = input()
K = int(input())
str_arr = []
for k in range(1, K + 1):
	for i in range(len(S) - k + 1):
		str_arr.append(S[i:i + k])
print(sorted(set(str_arr))[K - 1])


import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

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

def INT():
	return int(input())

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

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

def ZIP(n):
	return list(zip(*(MAP() for _ in range(n))))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
s = input()
K = INT()
substr = []
for l in range(len(s)):
	r = l + 1
	while r < len(s) + 1:
		if bisect(substr, s[l:r]) == 5:
			break
		elif s[l:r] in substr:
			r += 1
		elif s[l:r] not in substr:
			insort(substr, s[l:r])
			substr = substr[:5]
			if s[l:r] in substr:
				r += 1
print(substr[K - 1])


s = input()
k = int(input())
n = len(s)
subst = set()
for i in range(n):
	for j in range(5):
		subst.add(s[i:i + j + 1])
ls = list(subst)
ls.sort()
print(ls[k - 1])


s = input()
k = int(input())
n = len(s)
c = set()
for i in range(n):
	t = s[i:i + 5]
	for j in range(1, 5 + 1):
		c.add(t[:j])
c = list(c)
c.sort()
print(c[k - 1])


s = input()
k = int(input())
str = []
p = 1
for i in range(k):
	for j in range(0, len(s) - i):
		str.append(s[j:j + i + 1])
str = list(set(str))
str.sort()
print(str[k - 1])


S = input()
N = len(S)
K = int(input())
ttl = []
for i in range(N):
	for j in range(N - i):
		ttl.append(S[j:j + i + 1])
	if i > K:
		break
ttl = sorted(list(set(ttl)))
print(ttl[K - 1])


s = str(input())
k = int(input())
subs = set()
for i in range(len(s)):
	for j in range(i + 1, i + k + 1):
		subs.add(s[i:j])
print(sorted(list(subs))[k - 1])


s = input()
K = int(input())
S = []
for i in range(len(s)):
	for k in range(K):
		S.append(s[i:i + k + 1])
S = list(set(S))
S.sort()
print(S[K - 1])


s = list(input())
K = int(input())
sub_list = []
for i in range(1, min(K + 1, len(s) + 1)):
	for j in range(len(s) - i + 1):
		sub = ''.join(s[j:j + i])
		if sub not in sub_list:
			sub_list.append(sub)
sub_list.sort()
print(sub_list[K - 1])


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

def substring(S):
	N = len(S)
	ls = []
	for i in range(1, min(6, N + 1)):
		for j in range(0, N - i + 1):
			ls.append(S[j:j + i])
	setls = set(ls)
	ls = list(setls)
	ls.sort()
	return ls
print(substring(s)[K - 1])


s = input()
K = int(input())
N = len(s)
l = []
cnt = 0
for i in range(N):
	for j in range(i + 1, min(i + K + 1, N + 1)):
		l.append(s[i:j])
l = list(set(l))
l.sort()
print(l[K - 1])


import sys
sys.setrecursionlimit(10 ** 9)
S = input()
K = int(input())
chars = sorted(set(S))
checked = set()

def dfs(s):
	for c in chars:
		if len(checked) >= K:
			return
		next_s = s + c
		if next_s not in checked and next_s in S:
			checked.add(next_s)
			if len(checked) == K:
				print(next_s)
				return
			elif len(next_s) <= len(S):
				dfs(next_s)
dfs('')


s = input()
k = int(input())
n = len(s)
a = []
for i in range(1, 6):
	for j in range(n):
		x = s[j:j + i]
		a.append(x)
ans = sorted(list(set(a)))
print(ans[k - 1])


S = input()
K = int(input())
ans = []
for i in range(len(S)):
	for j in range(K):
		ans.append(S[i:i + j + 1])
ans = list(set(ans))
ans.sort()
print(ans[K - 1])


from collections import defaultdict
import string
s = input()
K = int(input())
location = defaultdict(list)
for (i, s_i) in enumerate(s):
	location[s_i].append(i)
count = 0
s_list = []
for c in string.ascii_lowercase[:26]:
	if location[c] == []:
		continue
	for idx in location[c]:
		for i in range(K):
			if idx + i + 1 > len(s):
				break
			if s[idx:idx + i + 1] in s_list:
				continue
			s_list.append(s[idx:idx + i + 1])
	count += 1
	if count == K:
		break
s_list.sort()
print(s_list[K - 1])


s = input()
K = int(input())
ops = set()
for i in range(min(len(s), 5)):
	for j in range(len(s) - i):
		ops.add(s[j:j + i + 1])
l = list(ops)
l.sort()
print(l[K - 1])


S = input()
K = int(input())
N = len(S)
s = set()
for i in range(N):
	for j in range(i + 1, min(i + K + 1, N + 1)):
		s |= {S[i:j]}
A = list(s)
A.sort()
print(A[K - 1])


S = input()
K = int(input())
tmp = set()
for i in range(len(S)):
	for j in range(5):
		tmp.add(S[i:i + j + 1])
print(sorted(tmp)[K - 1])


s = input()
K = int(input())
l = set()
for i in range(1, 6):
	l |= set([s[n:n + i] for n in range(len(s))])
print(sorted(l)[K - 1])


s = input()
k = int(input())
sub = []
for i in range(len(s)):
	for j in range(i, i + k + 1):
		sub.append(s[i:j])
print(sorted(set(sub))[k])


import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007

def main():
	S = readline().strip()
	K = int(readline())
	subs = set()
	for i in range(len(S)):
		for j in range(i + 1, min(len(S) + 1, i + K + 1)):
			subs.add(S[i:j])
	subs = sorted(subs)
	print(subs[K - 1])
	return

def __starting_point():
	main()
__starting_point()


s = input()
k = int(input())
subs_list = []
for i in range(len(s)):
	for j in range(i + 1, i + k + 1):
		subs_list.append(s[i:j])
ans = sorted(set(subs_list))
print(ans[k - 1])


def main():
	s = input()
	k = int(input())
	a = set()
	for l in range(5):
		for i in range(len(s) - l):
			a.add(s[i:i + l + 1])
	print(sorted(a)[k - 1])

def __starting_point():
	main()
__starting_point()


s = input()
K = int(input())
if K == 1:
	print(sorted(s)[0])
	return
topK = sorted(s)[:min(K, len(s))]
indices = []
for i in range(len(s)):
	if s[i] in topK:
		indices.append(i)
selected = []
for j in range(len(indices)):
	i = indices[j]
	tmp = []
	for k in range(min(K, len(s) - i)):
		tmp.append(s[i:i + k + 1])
	selected.extend(tmp)
selected = sorted(set(selected))
print(selected[K - 1])


s = input()
K = int(input())
sub = {s}
for d in range(1, K + 1):
	for i in range(len(s) - d + 1):
		sub |= {s[i:i + d]}
print(sorted(sub)[K - 1])


s = str(input())
k = int(input())
check = []
for i in range(len(s)):
	for j in range(k):
		check.append(s[i:i + j + 1])
print(sorted(list(set(check)))[k - 1])


import sys
stdin = sys.stdin
ip = lambda : int(sp())
fp = lambda : float(sp())
lp = lambda : list(map(int, stdin.readline().split()))
sp = lambda : stdin.readline().rstrip()
yp = lambda : print('Yes')
np = lambda : print('No')
s = list(sp())
k = ip()
ans = set()
alpa = list(set(s))
alpa.sort()
ch = 0
siyou = []
for i in range(len(alpa)):
	if i <= 2:
		siyou.append(alpa[i])
	else:
		break
for x in siyou:
	for i in range(len(s)):
		if s[i] == x:
			st = ''
			for y in range(i, i + 5):
				if y < len(s):
					st += s[y]
					ans.add(st)
	if len(ans) > k:
		break
ans = list(ans)
ans.sort()
print(ans[k - 1])


S = input()
K = int(input())
subs = []
for i in range(1, K + 1):
	for j in range(len(S) - i + 1):
		subs.append(S[j:j + i])
print(list(sorted(set(subs)))[K - 1])


s = input()
print(sorted({s[I // 6:I // 6 + I % 6] for I in range(len(s) * 6)})[int(input())])


from itertools import *
s = input()
k = int(input())
print(sorted(set((s[i:j] for (i, j) in combinations(range(len(s) + 1), 2) if j - i <= k)))[k - 1])


s = input()
k = int(input())
se = set()
for i in s:
	se.add(i)
if len(s) > 1:
	for i in range(len(s) - 1):
		se.add(s[i] + s[i + 1])
if len(s) > 2:
	for i in range(len(s) - 2):
		se.add(s[i] + s[i + 1] + s[i + 2])
if len(s) > 3:
	for i in range(len(s) - 3):
		se.add(s[i] + s[i + 1] + s[i + 2] + s[i + 3])
if len(s) > 4:
	for i in range(len(s) - 4):
		se.add(s[i] + s[i + 1] + s[i + 2] + s[i + 3] + s[i + 4])
se = sorted(se)
print(se[k - 1])


s = input()
k = int(input())
st = [s[i:i + j + 1] for i in range(len(s)) for j in range(k + 1)]
se = set(st)
a = list(se)
a.sort()
print(a[k - 1])


s = input()
k = int(input())
a = []
for i in range(len(s)):
	for j in range(i + 1, len(s) + 1):
		if j - i >= 6:
			break
		a.append(s[i:j])
res = sorted(set(a))
print(res[k - 1])


def main2():
	S = list(input())
	K = int(input())
	N = len(S)
	P = sorted(S)
	l = []
	a = []
	k = 0
	while len(l) <= 5 and k < N:
		if P[k] not in a:
			a.append(P[k])
			for n in range(N):
				if S[n] == P[k]:
					for i in range(1, 6):
						if n + i <= N:
							tmp = ''.join(S[n:n + i])
							if tmp not in l:
								l.append(tmp)
		k += 1
	l.sort()
	print(l[K - 1])

def __starting_point():
	main2()
__starting_point()


s = input()
k = int(input())
data = set()
for i in range(len(s)):
	for j in range(i, i + k):
		data.add(s[i:j + 1])
data = sorted(data)
print(data[k - 1])


S = input()
N = len(S)
K = int(input())
ngrams = set(S)
for n in range(2, 6):
	for i in range(N - n + 1):
		ngrams.add(S[i:i + n])
print(sorted(ngrams)[K - 1])


s = input()
k = int(input())
substring = set([])
for i in range(min(len(s), 5)):
	for j in range(0, len(s) - i):
		substring.add(s[j:i + j + 1])
ans = list(substring)
ans.sort()
print(ans[k - 1])


s = str(input())
K = int(input())
str_list = set()
for i in range(len(s) + 1):
	for j in range(i + 1, i + K + 1):
		if j > len(s):
			break
		str_list.add(s[i:j])
str_list = list(str_list)
str_list.sort()
print(str_list[K - 1])


s = input()
k = int(input())
n = len(s)
r = []
for right in range(0, n):
	for left in range(right + 1, right + k + 1):
		r.append(s[right:left])
print(sorted(set(r))[k - 1])


a = input()
k = int(input())
sstr = set()
for i in range(len(a)):
	for j in range(i + 1, i + k + 1):
		sstr.add(a[i:j])
sstr = sorted(sstr)
print(sstr[k - 1])


s = input()
K = int(input())
sub = set()
for k in range(1, 6):
	for i in range(len(s)):
		sub.add(s[i:i + k])
sub = sorted(list(sub))
print(sub[K - 1])


s = input()
k = int(input())
l = len(s)
a = {s[i:i + j + 1] for i in range(l) for j in range(k + 1)}
a = list(a)
a.sort()
print(a[k - 1])


s = input()
r = []
for i in range(1, 6):
	for j in range(len(s) - i + 1):
		r.append(s[j:j + i])
print(sorted(set(r))[int(input()) - 1])


S = input()
N = len(S)
K = int(input())
cnt = {i: [] for i in range(N)}
for i in range(N):
	for j in range(N - i):
		s = S[j:j + i + 1]
		l = len(s)
		if s not in cnt[l - 1]:
			cnt[l - 1].append(s)
	if i > K:
		break
ttl = []
for (k, v) in cnt.items():
	ttl.extend(v)
ttl.sort()
print(ttl[K - 1])


S = input()
K = int(input())
print(sorted(set((S[j:j + i + 1] for j in range(len(S)) for i in range(K))))[K - 1])


s = input()
n = len(s)
k = int(input())
l = set()
for t in range(1, k + 1):
	for i in range(max(n - t + 1, 0)):
		l.add(s[i:i + t])
a = list(l)
a.sort()
print(a[k - 1])


S = input()
k = int(input())
abc = []
for i in range(len(S)):
	for j in range(1, k + 1):
		if i + j <= len(S):
			s = S[i:i + j]
			if not s in abc:
				abc.append(S[i:i + j])
abc = sorted(abc)
print(abc[k - 1])


s = input()
k = int(input())
n = len(s)
L = []
for i in range(n):
	for j in range(1, 6):
		l = s[i:min(i + j, n)]
		L.append(l)
print(sorted(set(L))[k - 1])


import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

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

def INT():
	return int(input())

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

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

def ZIP(n):
	return list(zip(*(MAP() for _ in range(n))))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
	s = input()
	K = INT()
	strings = set()
	for i in range(1, K + 1):
		for j in range(len(s) - i + 1):
			strings.add(s[j:j + i])
	print(sorted(strings)[K - 1])

def __starting_point():
	main()
__starting_point()


s = input()
K = int(input())
T = list(s)
for i in range(2, 6):
	for j in range(len(s) - i + 1):
		T.append(s[j:j + i])
T = list(set(T))
T.sort()
print(T[K - 1])


s = input()
k = int(input())
u = [s[i:i + j + 1] for i in range(len(s)) for j in range(k + 1)]
a = list(set(u))
a.sort()
print(a[k - 1])


s = input()
k = int(input())
li = []
for i in range(len(s)):
	for j in range(i + 1, len(s) + 1):
		if j - i <= 6:
			li += [s[i:j]]
li2 = set(li)
li3 = sorted(li2)
print(li3[k - 1])


st = input()
k = int(input())
ls = set()
for i in range(5):
	for j in range(len(st) - i):
		ls.add(st[j:j + i + 1])
ls = list(ls)
ls.sort()
print(ls[k - 1])


s = list(input())
K = int(input())
L = []
for i in range(1, K + 1):
	for j in range(0, len(s) - i + 1):
		L.append(''.join(s[j:j + i]))
L = sorted(set(L))
print(L[K - 1])


s = input()
k = int(input())
sub = []
for i in range(len(s)):
	for j in range(i, i + 5):
		sub.append(s[i:j + 1])
sub = list(set(sub))
sub.sort()
print(sub[k - 1])


s = input()
k = int(input())
l = set()
for i in range(1, 6):
	l |= set([s[n:n + i] for n in range(0, len(s))])
print(sorted(list(l))[k - 1])


s = input()
d = ['z' * 5010] * 5
k = int(input())
for i in range(len(s)):
	for j in range(i, i + k):
		x = s[i:j + 1]
		if x in d or x == '':
			continue
		l = 0
		while l < 5 and x > d[l]:
			l += 1
		if l < 5:
			d = d[0:l] + [x] + d[l:]
			d = d[0:5]
print(d[k - 1])


S = input()
K = int(input())
substrings = set()
for length in range(1, K + 1):
	for i in range(len(S) - length + 1):
		substrings.add(S[i:i + length])
substrings = sorted(substrings)
print(substrings[K - 1])


s = input()
N = len(s)
K = int(input())
ss = set()
for i in range(N):
	for j in range(K):
		if i + j < N:
			ss.add(s[i:i + j + 1])
print(sorted(ss)[K - 1])


S = input()
K = int(input())
lst = set()
for i in range(len(S)):
	for j in range(1, K + 1):
		lst.add(S[i:i + j])
res = sorted(list(lst))
print(res[K - 1])


s = input()
K = int(input())
N = len(s)
ans = []
for i in range(min(K, N)):
	for j in range(N - i):
		ans.append(s[j:j + i + 1])
ans.sort()
count = 0
now = '0'
for i in range(len(ans)):
	if ans[i] != now:
		count += 1
		now = ans[i]
		if count == K:
			print(now)
			return


s = input().strip()
K = int(input())
substr = set()
for i in range(len(s)):
	for j in range(1, K + 1):
		substr.add(s[i:i + j])
print(sorted(substr)[K - 1])


S = input()
K = int(input())
P = set()
for i in range(len(S)):
	for k in range(K + 1):
		sub = S[i:k + i]
		P.add(sub)
P = sorted(list(P))
print(P[K])


s = input()
K = int(input())
l = {s}
for n in range(1, K + 1):
	for i in range(0, len(s) - n + 1):
		l.add(s[i:i + n])
l = list(l)
l.sort()
print(l[K - 1])


s = input()
k = int(input())
A = []
for i in range(1, 6):
	for j in range(len(s) - i + 1):
		A.append(s[j:j + i])
A = sorted(set(A))
print(A[k - 1])


s = input()
a = int(input())
r = []
for i in range(len(s)):
	for j in range(i + 1, min(a + i, len(s)) + 1):
		r.append(s[i:j])
r = list(set(r))
r.sort()
print(r[a - 1])


s = input()
print(sorted({s[I // 6:I // 6 + I % 6] for I in range(30000)})[int(input())])


s = input()
k = int(input())
set_a = set()
for i in range(len(s) + 1):
	for j in range(i + 1, min(len(s) + 1, i + k + 1)):
		set_a.add(s[i:j])
print(sorted(set_a)[k - 1])


S = list(input())
n = len(S)
k = int(input())
H = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
p = 0
cnt = 0
D = set()
while True:
	for i in range(n):
		if S[i] == H[p]:
			for j in range(1, 6):
				if i + j <= n:
					D.add(''.join(S[i:i + j]))
	p += 1
	if len(list(D)) >= k:
		break
D = list(D)
D.sort()
print(D[k - 1])


s = list(input())
k = int(input())
s.append('')
Dict = {}
dict_keys = []
for left in range(len(s)):
	for right in range(left + 1, len(s)):
		string = ''.join(s[left:right])
		if len(string) > k:
			break
		if string not in Dict.keys():
			Dict[string] = True
Dict = sorted(Dict.keys())
print(Dict[k - 1])


S = input()
k = int(input())
A = []
for i in range(len(S)):
	for j in range(i + 1, i + k + 1):
		A.append(S[i:j])
ans = sorted(list(set(A)))
print(ans[k - 1])


str = input()
K = int(input())
s = set()
for scope in range(1, K + 1):
	for f in range(len(str) - scope + 1):
		s.add(str[f:f + scope])
print(sorted([x for x in s])[K - 1])


(s, K) = open(0).read().split()
K = int(K)
ss = set()
temp = set([''])
for x in s:
	temp = set([''.join((y, x)) for y in temp if len(y) <= 4])
	ss = ss | temp
	temp.add('')
l = list(ss)
l.sort()
print(l[K - 1])


S = input()
k = int(input())
ss = []
for i in range(len(S)):
	for j in range(i + 1, min(i + k + 1, len(S) + 1)):
		ss.append(S[i:j])
ss = sorted(list(set(ss)))
print(ss[k - 1])


def main():
	s = input()
	K = int(input())
	r = set()
	for i in range(97, 97 + 26):
		for (j, v) in enumerate(s):
			if v == chr(i):
				for k in range(5):
					r.add(s[j:j + k + 1])
		if len(r) > 5:
			break
	l = list(r)
	l.sort()
	return l[K - 1]
print(main())


s = input()
k = int(input())
l = k
count = 0
n = len(s)
lst = 'abcdefghijklmnopqrstuvwxyz'
for alpha in lst:
	alpha_index = []
	for index in range(n):
		if alpha == s[index]:
			alpha_index.append(index)
	if len(alpha_index) > 0:
		cand_lst = []
		for index2 in alpha_index:
			end_lst = [index2 + m for m in range(1, 6) if index2 + m <= n]
			for end in end_lst:
				cand_lst.append(s[index2:end])
		cand_lst = set(cand_lst)
		cand_lst = sorted(cand_lst)
		if len(cand_lst) < l:
			l = l - len(cand_lst)
		else:
			res = cand_lst[l - 1]
			break
print(res)


s = input()
K = int(input())
list = []
for i in range(K):
	for j in range(len(s) - i):
		if s[j:j + i + 1] not in list:
			list.append(s[j:j + i + 1])
list.sort()
print(list[K - 1])


s = input()
k = int(input())
x = set()
for i in range(1, 6):
	for j in range(len(s) - i + 1):
		x.add(s[j:i + j])
y = sorted(list(x))
print(y[k - 1])


s = input()
k = int(input())
se = set()
for i in range(len(s)):
	for j in range(1, k + 1):
		se.add(s[i:i + j])
li = list(se)
li.sort()
print(li[k - 1])


s = input()
k = int(input())
t = set()
for i in range(len(s)):
	tt = ''
	for j in range(i, min(i + 5, len(s))):
		tt += s[j]
		t.add(tt)
print(sorted(t)[k - 1])


s = input()
k = int(input())
l = 'abcdefghijklmnopqrstuvwxyz'
d = {}
for i in range(26):
	cnt = s.count(l[i])
	pre = 0
	if cnt > 0:
		for j in range(cnt):
			pos = s.find(l[i], pre)
			pre = pos + 1
			for m in range(min(len(s) - pos, k)):
				if s[pos:pos + m + 1] not in d:
					d[s[pos:pos + m + 1]] = 1
	if len(d) >= k:
		dl = []
		for i in d.keys():
			dl.append(i)
		dl.sort()
		print(dl[k - 1])
		return


s = list(input())
k = int(input())
t = set({})
for i in range(min(k, len(s))):
	for j in range(len(s) - i):
		t.add(''.join(s[j:i + j + 1]))
print(sorted(t)[k - 1])


s = input()
K = int(input())
ans = [s[l:l + r + 1] for l in range(len(s)) for r in range(K)]
print(sorted(set(ans))[K - 1])


s = input()
k = int(input())
n = len(s)
t = set()
for i in range(k):
	for j in range(n - i):
		t.add(s[j:j + i + 1])
lis = sorted(list(t))
print(lis[k - 1])


s = input()
k = int(input())
r = set()
for i in range(1, 6):
	for j in range(len(s) - i + 1):
		r.add(s[j:j + i])
l = list(r)
l = sorted(l)
print(l[k - 1])


s = input()
K = int(input())
sss = set()
M = len(s)
for end in range(1, K + 1):
	for i in range(M):
		sss.add(s[i:i + end])
ans = sorted(sss)
print(ans[K - 1])


s = input()
K = int(input())
arr = set()
for i in range(len(s)):
	for j in range(i + 1, min(i + 1 + K, len(s) + 1)):
		arr.add(s[i:j])
print(sorted(arr)[K - 1])


s = input()
K = int(input())
se = set()
for L in range(1, K + 1):
	for i in range(len(s)):
		se.add(s[i:i + L])
li = list(se)
li.sort()
print(li[K - 1])


s = input()
K = int(input())
substrings = {s[i:j]: 0 for i in range(len(s)) for j in range(i + 1, min(i + 1 + K, len(s) + 1))}
print(sorted(substrings)[K - 1])


(s, k) = (input(), int(input()))
L = []
for i in range(0, k):
	L += [s[j:j + i + 1] for j in range(len(s) - i + 1)]
L = sorted(list(set(L)))
L.remove('')
print(L[k - 1])


s = input()
K = int(input())
S = []
n = len(s)
for i in range(n):
	for j in range(i + 1, i + K + 1):
		S.append(s[i:j])
S = list(set(S))
S.sort()
print(S[K - 1])


S = input()
K = int(input())
A = []
for i in range(len(S)):
	for j in range(1, 6):
		a = S[i:i + j]
		A.append(a)
A = set(A)
A = sorted(set(A))
print(A[K - 1])


s = input()
K = int(input())
subst = []
for i in range(5):
	for j in range(len(s) - i):
		subst.append(s[j:j + i + 1])
subst = list(set(subst))
subst.sort()
print(subst[K - 1])


S = input()
K = int(input())
N = len(S)
memo = []
for i in range(N):
	for d in range(1, min(K, N - i) + 1):
		memo.append(S[i:i + d])
print(sorted(set(memo))[K - 1])


s = input()
k = int(input())
se = set()
for i in range(len(s) + 1):
	for j in range(i, i + k + 1):
		se.add(s[i:j])
se.remove('')
l = sorted(list(se))
print(l[k - 1])


s = input()
K = int(input())
words = set()
for i in range(1, 6):
	for j in range(len(s) - i + 1):
		words.add(s[j:j + i])
print(sorted(words)[K - 1])


S = input()
K = int(input())
sub = set(S)
for step in range(2, 6):
	for i in range(0, len(S) - step + 1):
		sub.add(S[i:i + step])
print(sorted(sub)[K - 1])


s = input()
K = int(input())
st = set()
for i in range(len(s)):
	for j in range(1, 6):
		st.add(s[i:i + j])
sl = sorted(list(st))
print(sl[K - 1])


s = input()
k = int(input())
subs = set()
for i in range(len(s)):
	for j in range(i + 1, min(i + 6, len(s) + 1)):
		sub = s[i:j]
		subs.add(sub)
print(sorted(list(subs))[k - 1])


S = input()
K = int(input())
subs = set()
for k in range(1, K + 1):
	for i in range(len(S)):
		subs.add(S[i:i + k])
print(sorted(subs)[K - 1])


s = input()
k = int(input())
ans = []
for i in range(len(s)):
	x = 0
	for j in range(5):
		if i + j < len(s):
			x += (ord(s[i + j]) - 96) * 10 ** (8 - 2 * j)
			ans.append((x, s[i:i + j + 1]))
ans = list(set(ans))
ans.sort()
print(ans[k - 1][1])


s = input()
n = len(s)
K = int(input())
ans = []
an = set()
for i in range(1, min(5, n) + 1):
	for j in range(n - i + 1):
		S = s[j:j + i]
		if S not in an:
			ans.append(S)
			an.add(S)
ans.sort()
print(ans[K - 1])


A = list(input())
K = int(input())
L = []
for i in range(len(A)):
	for j in range(i + 1, i + K + 1):
		L.append(''.join(A[i:j]))
L = list(set(L))
L.sort()
print(L[K - 1])


S = input()
K = int(input())
P = set()
for k in range(1, K + 1):
	for i in range(len(S)):
		s = S[i:i + k]
		P.add(s)
P = sorted(P)
ans = P[K - 1]
print(ans)


s = input()
k = int(input())
L = len(s)
ss = []
for i in range(L):
	for j in range(1, k + 1):
		ss.append(s[i:i + j])
t = set(ss)
u = list(t)
u.sort()
print(u[k - 1])


s = input().rstrip()
k = int(input())
n = len(s)
ss = set()
for i in range(n):
	for j in range(1, k + 1):
		ss.add(s[i:i + j])
print(sorted(ss)[k - 1])


s = input()
k = int(input())
n = len(s)
S = set()
for i in range(n):
	for j in range(min(k, n - i)):
		S.add(s[i:i + j + 1])
print(sorted(S)[k - 1])


s = input()
K = int(input())
ss = set()
n = len(s)
for x in range(1, K + 1):
	for i in range(n):
		ss.add(s[i:i + x])
print(sorted(ss)[K - 1])


s = input()
k = int(input())
sset = set()
for i in range(1, 6):
	sset |= set([s[j:j + i] for j in range(0, len(s))])
print(sorted(sset)[k - 1])


w = input()
n = int(input())
print(sorted({w[j:j + i + 1] for i in range(n) for j in range(len(w) - i)})[n - 1])


s = input()
K = int(input())
sub = set()
for i in range(len(s)):
	for j in range(i + 1, i + K + 1):
		sub.add(s[i:j])
ans = list(sorted(sub))
print(ans[K - 1])


s = input()
k = int(input())
c = []
for i in range(len(s)):
	for j in range(k):
		c.append(s[i:i + j + 1])
c.sort()
pre = ''
for x in c:
	if pre == x:
		continue
	k -= 1
	if k == 0:
		print(x)
		break
	pre = x


s = input()
K = int(input())
a = []
l = len(s)
for i in range(l):
	for j in range(1, K + 1):
		a.append(s[i:i + j])
a = list(set(a))
a.sort()
print(a[K - 1])


s = input()
K = int(input())
seq = set()
l = len(s)
for i in range(l):
	for j in range(1, K + 1):
		seq.add(s[i:i + j])
seq = list(seq)
seq.sort()
print(seq[K - 1])


s = input()
K = int(input())
ss = []
for l in range(1, min(K, len(s)) + 1):
	ss += sorted({s[i:i + l] for i in range(0, len(s) - l + 1)})[:K]
r = sorted(ss)[K - 1]
print(r)


from collections import deque

def search(moji):
	num = len(moji)
	setsn = set([])
	for i in range(len(s) - num + 1):
		if s[i:i + num] == moji:
			str_ = s[i:i + num + 1]
			if len(str_) == num + 1:
				setsn.add(str_)
	sorted_setsn = sorted(setsn, reverse=True)
	return sorted_setsn
s = str(input())
k = int(input())
n = len(s)
sets1 = set([])
for i in range(0, len(s)):
	sets1.add(s[i])
sorted_sets1 = sorted(sets1)
dq = deque(sorted_sets1)
while len(dq):
	moji = dq.popleft()
	k -= 1
	if k == 0:
		print(moji)
		return
	sorted_setsn = search(moji)
	dq.extendleft(sorted_setsn)


s = input()
k = int(input())
d = set()
for n in range(1, 6):
	for i in range(len(s)):
		if i + n <= len(s):
			d.add(s[i:i + n])
sd = sorted(d)
print(sd[k - 1])


s = input()
k = int(input())
lst = []
ls = len(s)
for i in range(ls):
	for j in range(i + 1, min(ls + 1, i + k + 1)):
		lst.append(s[i:j])
lst = sorted(set(lst))
print(lst[k - 1])


def main():
	s = input()
	N = len(s)
	K = int(input())
	X = set()
	for i in range(1, K + 1):
		for j in range(N - i + 1):
			X.add(s[j:j + i])
	print(sorted(X)[K - 1])

def __starting_point():
	main()
__starting_point()


s = input()
K = int(input())
x = []
for i in range(5):
	x.extend(list({s[j:j + i + 1] for j in range(len(s) - i)}))
x = sorted(x)
print(x[K - 1])


def main():
	S = input()
	k = int(input())
	setS = set(list(S))
	count = 0
	ans = []
	for j in range(1, k + 1):
		for i in range(len(S) - j + 1):
			ans.append(S[i:i + j])
	ans = sorted(list(set(ans)))
	print(ans[k - 1])

def __starting_point():
	main()
__starting_point()


s = input().strip()
k = int(input())
subs = set()
for i in range(1, 6):
	for j in range(0, len(s) - i + 1):
		subs |= set([s[j:j + i]])
print(list(sorted(subs))[k - 1])


s = input()
K = int(input())
N = len(s)
S = set()
for i in range(N):
	for j in range(i + 1, min(i + 6, N + 1)):
		S.add(s[i:j])
l = sorted(list(S))
print(l[K - 1])


S = input()
K = int(input())
check = []
for i in range(len(S)):
	for k in range(1, K + 1):
		check.append(S[i:i + k])
check = sorted(list(set(check)))
print(check[K - 1])


s = input()
k = int(input())
c = []
for i in range(1, 6):
	for j in range(len(s)):
		if s[j:j + i] not in c:
			c.append(s[j:j + i])
c.sort()
print(c[k - 1])


S = input()
K = int(input())
lset = set([])
for i in range(min(len(S), K)):
	for j in range(len(S) - i):
		lset.add(S[j:j + i + 1])
llist = list(lset)
llist.sort()
print(llist[K - 1])


s = input()
k = int(input())
print(sorted(list({s[i:i + f] for i in range(len(s)) for f in range(1, k + 1)}))[k - 1])


s = input()
k = int(input())
ls = len(s)
res = []
for i in range(1, k + 1):
	for j in range(ls - i + 1):
		res.append(s[j:j + i])
ress = sorted(list(set(res)))
print(ress[k - 1])


s = input()
K = int(input())
se = set()
for i in range(1, min(len(s) + 1, K + 1)):
	for j in range(len(s) - i + 1):
		se.add(s[j:j + i])
print(sorted(list(se))[K - 1])


S = input()
N = int(input())
res = set()
for i in range(len(S)):
	for j in range(5):
		res.add(S[i:i + j + 1])
print(sorted(res)[N - 1])


s = str(input())
k = int(input())
l = []
for i in range(len(s)):
	for j in range(1, k + 1):
		l.append(s[i:i + j])
print(sorted(set(l))[k - 1])


S = input()
K = int(input())
s = set()
for L in range(1, K + 1):
	for j in range(len(S)):
		s.add(S[j:L + j])
ss = sorted(list(s))
print(ss[K - 1])


import sys
from collections import defaultdict
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7

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

def main():
	S = input()
	N = len(S)
	K = int(input())
	places = defaultdict(list)
	for i in range(N):
		places[S[i]].append(i)
	places = sorted(list(places.items()), key=lambda x: x[0])
	words = set()
	for (k, v) in places:
		for start in v:
			cnt = 0
			for end in range(start + 1, N + 1):
				words.add(S[start:end])
				cnt += 1
				if cnt == 5:
					break
		if len(words) >= 5:
			break
	words = sorted(words)
	print(words[K - 1])

def __starting_point():
	main()
__starting_point()


s = input()
k = int(input())
lst = sorted(list(set(s)))
tank = []
for tg in lst:
	for i in range(len(s)):
		if s[i] == tg:
			for j in range(k):
				if i + j <= len(s) and s[i:i + j + 1] not in tank:
					tank.append(s[i:i + j + 1])
	if len(tank) >= k:
		break
tank.sort()
print(tank[k - 1])


S = input()
N = len(S)
K = int(input())
S_list = sorted(set(list(S)))
memo = {}
for small_char in S_list:
	for i in range(N):
		if S[i] == small_char:
			for j in range(i + 1, i + K + 1):
				word = S[i:j]
				memo[word] = None
	if len(memo) >= K:
		break
ans_list = sorted(list(memo.keys()))
print(ans_list[K - 1])


import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import defaultdict

def main():
	s = list(input())
	k = int(input())
	k -= 1
	d1 = defaultdict(list)
	for (i, c) in enumerate(s):
		d1[c].append(i)
	d2 = sorted(d1.items())
	lens = len(s)
	for d2e in d2:
		subs = set()
		subs.add(d2e[0])
		for d2ee in d2e[1]:
			end = min(lens + 1, d2ee + k + 2)
			for i1 in range(d2ee + 1, end):
				subs.add(''.join(s[d2ee:i1]))
		if len(subs) > k:
			subsl = list(subs)
			subsl.sort()
			print(subsl[k])
			return
		else:
			k -= len(subs)

def __starting_point():
	main()
__starting_point()


s = input()
k = int(input())
c = []
for i in range(1, min(k + 1, len(s) + 1)):
	for j in range(len(s) - i + 1):
		c.append(s[j:j + i])
c = sorted(set(c))
print(c[k - 1])


S = input()
l = len(S)
d = set()
K = int(input())
for i in range(5):
	for j in range(l - i):
		d.add(S[j:j + i + 1])
D = sorted(list(d))
print(D[K - 1])


s = input()
k = int(input())
t = len(s)
v = []
for i in range(0, t):
	for j in range(i, min(t, i + 5)):
		v.append(s[i:j + 1])
v = sorted(set(v))
print(v[k - 1])


s = input()
K = int(input())
subs = set()
L = len(s)
for l in range(1, min(L, 5) + 1):
	for i in range(L - l + 1):
		subs.add(s[i:i + l])
print(sorted(list(subs))[K - 1])