Ashton appeared for a job interview and is asked the following question. Arrange all the distinct substrings  of a given string in lexicographical order and concatenate them. Print the $k^{th}$ character of the concatenated string. It is assured that given value of $\boldsymbol{\mbox{k}}$ will be valid i.e. there will be a $k^{th}$ character. Can you help Ashton out with this?  

For example, given the string $s=\mathtt{abc}$, its distinct substrings are $[a,\:ab,\:abc,\:abcd,\:b,\:bc,\:bcd,\:c,\:cd,\:d]$.  Sorted and concatenated, they make the string $aababcabcdbbcbcdccdd$.  If $K=5$ then, the answer is $\boldsymbol{b}$, the $5^{th}$ character of the 1-indexed concatenated string.  

Note We have distinct substrings here, i.e. if string is aa, it's distinct substrings are a and aa.  

Function Description  

Complete the ashtonString function in the editor below.  It should return the $k^{th}$ character from the concatenated string, 1-based indexing.  

ashtonString has the following parameters: 

- s: a string 

- k: an integer  

Input Format

The first line will contain an integer $\boldsymbol{\boldsymbol{t}}$, the number of test cases.  

Each of the subsequent $\boldsymbol{\boldsymbol{t}}$ pairs of lines is as follows: 

- The first line of each test case contains a string, $\boldsymbol{\mathrm{~S~}}$. 

- The second line contains an integer, $\boldsymbol{\mbox{k}}$.  

Constraints

$1\leq t\leq5$ 

$1\leq|s|\leq10^5$ 

Each character of string $s\in a s c i i[a-z]$ 

$\boldsymbol{\mbox{k}}$ will be an appropriate integer. 

Output Format

Print the $k^{th}$ character (1-based index) of the concatenation of the ordered distinct substrings of $\boldsymbol{\mathrm{~S~}}$.

Sample Input
1
dbac
3

Sample Output
c

Explanation

The substrings when arranged in lexicographic order are as follows   

a, ac, b, ba, bac, c, d, db, dba, dbac

On concatenating them, we get 

aacbbabaccddbdbadbac

The third character in this string is c.

Source: hackerrank | Difficulty: HARD
Tags: String algorithms


Solutions:
import sys

def rendez(s, slen, l, l_first, l_last, diffstart):
	if l_first >= l_last:
		return
	diffstart1 = diffstart
	while True:
		sm_ord_min = ord('z') + 1
		sm_ord_max = ord('a') - 2
		for l_i in range(l_first, l_last + 1):
			sm_ord = ord(s[l[l_i] + diffstart1]) if l[l_i] + diffstart1 < slen else ord('a') - 1
			if sm_ord < sm_ord_min:
				sm_ord_min = sm_ord
			if sm_ord > sm_ord_max:
				sm_ord_max = sm_ord
		if sm_ord_min == sm_ord_max:
			diffstart1 += 1
		else:
			break
	sm = chr(int((sm_ord_min + sm_ord_max + 1) / 2))
	i1 = l_first
	i2 = l_last
	try:
		while i1 < i2:
			if l[i1] + diffstart1 == slen or s[l[i1] + diffstart1] < sm:
				i1 += 1
			elif l[i2] + diffstart1 < slen and s[l[i2] + diffstart1] >= sm:
				i2 -= 1
			else:
				ll = l[i1]
				l[i1] = l[i2]
				l[i2] = ll
				i1 += 1
	except:
		print((slen, l_first, l_last, i1, i2, l[i1], l[i2], diffstart, sm))
		return
	rendez(s, slen, l, l_first, i1 - 1, diffstart1)
	rendez(s, slen, l, i1, l_last, diffstart1)

def testcase(s, k):
	slenarray = [0] * (len(s) + 1)
	for i in range(1, len(s) + 1):
		slenarray[i] = slenarray[i - 1] + i
	l = list(range(len(s)))
	rendez(s, len(s), l, 0, len(l) - 1, 0)
	for i in range(len(s)):
		s0 = s[l[i - 1]:] if i > 0 else ''
		s1 = s[l[i]:]
		diffstart = 0
		while diffstart < len(s0) and diffstart < len(s1) and (s0[diffstart] == s1[diffstart]):
			diffstart = diffstart + 1
		slen = slenarray[len(s1)] - slenarray[diffstart]
		if k <= slen:
			d = diffstart + 1
			while k > 0:
				if k <= d:
					print(s1[k - 1])
					k = 0
					break
				else:
					k = k - d
					d = d + 1
		else:
			k = k - slen
		if k == 0:
			break
testcount = int(sys.stdin.readline())
for i in range(testcount):
	s = sys.stdin.readline()[:-1]
	k = int(sys.stdin.readline())
	testcase(s, k)


import sys

def rendez(s, slen, l, l_first, l_last, diffstart):
	if l_first >= l_last:
		return
	diffstart1 = diffstart
	while True:
		sm_ord_min = ord('z') + 1
		sm_ord_max = ord('a') - 2
		for l_i in range(l_first, l_last + 1):
			sm_ord = ord(s[l[l_i] + diffstart1]) if l[l_i] + diffstart1 < slen else ord('a') - 1
			if sm_ord < sm_ord_min:
				sm_ord_min = sm_ord
			if sm_ord > sm_ord_max:
				sm_ord_max = sm_ord
		if sm_ord_min == sm_ord_max:
			diffstart1 += 1
		else:
			break
	sm = chr(int((sm_ord_min + sm_ord_max + 1) / 2))
	i1 = l_first
	i2 = l_last
	try:
		while i1 < i2:
			if l[i1] + diffstart1 == slen or s[l[i1] + diffstart1] < sm:
				i1 += 1
			elif l[i2] + diffstart1 < slen and s[l[i2] + diffstart1] >= sm:
				i2 -= 1
			else:
				ll = l[i1]
				l[i1] = l[i2]
				l[i2] = ll
				i1 += 1
	except:
		print((slen, l_first, l_last, i1, i2, l[i1], l[i2], diffstart, sm))
		return
	rendez(s, slen, l, l_first, i1 - 1, diffstart1)
	rendez(s, slen, l, i1, l_last, diffstart1)

def testcase(s, k):
	slenarray = [0] * (len(s) + 1)
	for i in range(1, len(s) + 1):
		slenarray[i] = slenarray[i - 1] + i
	l = list(range(len(s)))
	rendez(s, len(s), l, 0, len(l) - 1, 0)
	for i in range(len(s)):
		s0 = s[l[i - 1]:] if i > 0 else ''
		s1 = s[l[i]:]
		diffstart = 0
		while diffstart < len(s0) and diffstart < len(s1) and (s0[diffstart] == s1[diffstart]):
			diffstart = diffstart + 1
		slen = slenarray[len(s1)] - slenarray[diffstart]
		if k <= slen:
			d = diffstart + 1
			while k > 0:
				if k <= d:
					print(s1[k - 1])
					k = 0
					break
				else:
					k = k - d
					d = d + 1
		else:
			k = k - slen
		if k == 0:
			break
testcount = int(sys.stdin.readline())
for i in range(testcount):
	s = sys.stdin.readline()[:-1]
	k = int(sys.stdin.readline())
	testcase(s, k)


def foo(text, k):
	stack = [('', list(range(len(text))))]
	while stack != []:
		(prefix, ii) = stack.pop()
		if k < len(prefix):
			return prefix[k]
		k -= len(prefix)
		cs = sorted([(text[i], i + 1) for i in ii if i < len(text)], reverse=True)
		i = 0
		while i < len(cs):
			c = cs[i][0]
			ii2 = [cs[i][1]]
			j = i + 1
			while j < len(cs) and cs[j][0] == c:
				ii2.append(cs[j][1])
				j += 1
			stack.append((prefix + c, ii2))
			i = j
	return None
T = int(input().strip())
for i in range(T):
	text = input().strip()
	k = int(input().strip())
	print(foo(text, k - 1))


n = int(input())
start_s = []
k = []
for i in range(n):
	start_s.append(input())
	k.append(int(input()))
for t in range(n):
	letters = sorted(set(start_s[t]))
	total_l = 0
	found = False
	x = 0
	while not found:
		s = letters[x]
		pos = []
		for i in range(len(start_s[t])):
			if start_s[t][i] == s:
				pos.append(i)
		long_str = [start_s[t][i:] for i in pos]
		long_str.sort()
		prev_ls = ''
		for ls in long_str:
			i = 0
			while i < len(ls) and i < len(prev_ls) and (ls[i] == prev_ls[i]):
				i += 1
			l = sum([j for j in range(i + 1, len(ls) + 1)])
			if total_l + l >= k[t]:
				j = i + 1
				len_substr = 0
				while len_substr < k[t] - total_l:
					len_substr += j
					j += 1
				sub_str = ls[:j - 1]
				print(sub_str[len(sub_str) - (len_substr - (k[t] - total_l)) - 1])
				found = True
				break
			else:
				total_l += l
			prev_ls = ls
		x += 1


def readInts():
	return map(int, input().strip().split())

def calc_sfxa(ns):
	n = len(ns)

	def rank_refine(width):
		ts = []
		for ix in range(n):
			v1 = ranks[ix]
			v2 = -1
			ix2 = ix + width
			if ix2 < n:
				v2 = ranks[ix2]
			t = ((v1, v2), ix)
			ts.append(t)
		ts.sort()
		rv = -1
		pv = (-1, -1)
		for t in ts:
			v = t[0]
			if v != pv:
				pv = v
				rv += 1
			ranks[t[1]] = rv
		return rv != n - 1

	def lcp():
		out = [0 for _ in range(n)]
		same = 0
		for ix1 in range(n):
			sfx_ix1 = ranks[ix1]
			if sfx_ix1 == n - 1:
				same = 0
				continue
			ix2 = sfxa[sfx_ix1 + 1]
			ixLo = min(ix1, ix2) + same
			ixHi = max(ix1, ix2) + same
			d = ixHi - ixLo
			for ixHii in range(ixHi, n):
				if ns[ixHii] != ns[ixHii - d]:
					break
				same += 1
			out[sfx_ix1] = same
			if same:
				same -= 1
		return out
	ranks = []
	az = 'abcdefghijklmnopqrstuvwxyz'
	az_d = {}
	for (i, c) in enumerate(az):
		az_d[c] = i
	for c in ns:
		ranks.append(az_d[c])
	width = 1
	while rank_refine(width):
		width *= 2
	sfxa = [0 for _ in range(n)]
	for (i, r) in enumerate(ranks):
		sfxa[r] = i
	return (sfxa, lcp())

def sumn(n):
	return n * (n + 1) // 2

def solve(k, ns):
	(sfxa, lcp) = calc_sfxa(ns)
	n = len(ns)
	ix = 0
	d = 0
	k -= 1
	while k >= d:
		k -= d
		next_len = n - sfxa[ix]
		d = sumn(next_len)
		if ix > 0:
			ld = lcp[ix - 1]
			d_dup = sumn(ld)
			d -= d_dup
		ix += 1
	ix -= 1
	k += sumn(lcp[ix - 1])
	x = int(((8 * k + 1) ** 0.5 - 1) / 2)
	k -= sumn(x)
	return ns[sfxa[ix] + k]
(q,) = readInts()
for _ in range(q):
	s = input()
	(k,) = readInts()
	print(solve(k, s))


import sys
from collections import defaultdict, Counter

def generate_suffixarray(thestr):
	d = defaultdict(list)
	for i in range(len(thestr)):
		d[thestr[i]].append(i)
	result = []
	for (k, v) in sorted(d.items()):
		if len(v) == 1:
			result.append(v[0])
		else:
			dd = defaultdict(list)
			for i in v:
				dd[thestr[i:]].append(i)
			for (k2, v2) in sorted(dd.items()):
				result.append(v2[0])
			del dd
	return result

def find_nth_char(thestr, k):
	sa = generate_suffixarray(thestr)
	prevsastr = ''
	for s in sa:
		cursastr = thestr[s:]
		offset = 1
		while prevsastr[0:offset] == cursastr[0:offset]:
			offset += 1
		for j in range(offset, len(cursastr) + 1):
			thesubstr = cursastr[0:j]
			lensubstr = len(thesubstr)
			if k > lensubstr:
				k -= lensubstr
			else:
				print(thesubstr[k - 1])
				return
		prevsastr = cursastr
cases = int(input().strip())
for _ in range(cases):
	givenstr = input().strip()
	k = int(input().strip())
	find_nth_char(givenstr, k)


def skr(mstr, lim):
	abet = 'abcdefghijklmnopqrstuvwxyz'
	rem = lim
	for c in abet:
		if c not in mstr:
			continue
		rem -= 1
		if rem == 0:
			return c
		ssl = [(mstr[i:], i) for i in range(len(mstr)) if mstr[i] == c]
		ssl.sort()
		ssl = [i[1] for i in ssl]
		for ssli in range(len(ssl)):
			idx = ssl[ssli]
			uniquel = 2
			for length in range(2, len(mstr) - idx + 1):
				for tssi in range(ssli):
					_idx = ssl[tssi]
					if mstr[_idx:_idx + length] == mstr[idx:idx + length]:
						break
				else:
					uniquel = length
					break
			for _len in range(uniquel, len(mstr) - idx + 1):
				if rem - _len <= 0:
					return mstr[idx + rem - 1]
				else:
					rem -= _len
	return None

def AS():
	runs = int(input())
	for _ in range(runs):
		iStr = input()
		dex = int(input())
		print(skr(iStr, dex))
AS()


ALPHABET = 'abcdefghijklmnopqrstuvwxyz'

def do_it(base, k):
	base_len = len(base)
	counter = 0
	for letter in ALPHABET:
		sorted_i = [i for i in range(base_len) if base[i] == letter]
		sorted_i.sort(key=lambda x: base[x:])
		prev = None
		for index in sorted_i:
			start = 0
			if prev != None:
				while max(index + start, prev + start) < base_len and base[index + start] == base[prev + start]:
					start += 1
			for length in range(start + 1, base_len - index + 1):
				if counter + length > k:
					return base[index + k - counter]
				counter += length
			prev = index
n = int(input())
for _ in range(n):
	base = input()
	k = int(input()) - 1
	print(do_it(base, k))


from collections import defaultdict

def func1(s, n):
	d = defaultdict(list)
	sl = len(s)
	for i in range(sl):
		d[s[i]].append(i)
	for i in sorted(d.keys()):
		d[i].sort(key=lambda x: s[x:])
		pre = None
		cm_len = 0
		for j in d[i]:
			nex = s[j:]
			ind = 0
			if pre:
				try:
					while nex[:ind] == pre[:ind]:
						ind += 1
				except:
					pass
			for l in range(ind, len(nex) + 1):
				z = l
				if n - z > 0:
					n -= z
				else:
					return nex[n - 1]
			pre = nex
for i in range(int(input())):
	x = func1(input().strip(), int(input()))
	print(x)


t = int(input().strip())
for i in range(t):
	s = input().strip()
	k = int(input().strip())
	nodes_to_visit = []
	char_to_indices = {}
	target_char = ''
	prefix = ''
	for (i, char) in enumerate(s):
		if char not in char_to_indices:
			char_to_indices[char] = []
		char_to_indices[char].append(i)
	for char in sorted(char_to_indices.keys(), reverse=True):
		nodes_to_visit.append((prefix, char, char_to_indices[char]))
	while nodes_to_visit:
		(prefix, char, indices) = nodes_to_visit.pop()
		c_to_i = {}
		for i in indices:
			if i + 1 < len(s):
				c = s[i + 1]
				if c not in c_to_i:
					c_to_i[c] = []
				c_to_i[c].append(i + 1)
		for c in sorted(c_to_i.keys(), reverse=True):
			nodes_to_visit.append((prefix + char, c, c_to_i[c]))
		if k <= len(prefix) + 1:
			target_char = (prefix + char)[k - 1]
			break
		k = k - len(prefix) - 1
	print(target_char)


def substring_from_index(string, idx):
	for i in range(idx + 1, len(string) + 1):
		yield string[:i]
	return

def substring_from_list(suffixes, k):
	suffixes.sort()
	substrs = ''
	last_suffix = ''
	for suffix in suffixes:
		if suffix == last_suffix:
			continue
		idx = 0
		if last_suffix != '':
			idx = 1
			while idx < len(suffix) and idx < len(last_suffix) and (last_suffix[idx] == suffix[idx]):
				idx = idx + 1
		for substr in substring_from_index(suffix, idx):
			if len(substr) < k:
				k = k - len(substr)
			else:
				return (substr[k], k)
		last_suffix = suffix
	return (None, k)
ALPHABET = ['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']

def make_suffix_dict(word):
	suffix_indexes = dict()
	for (i, ch) in enumerate(word):
		if ch not in suffix_indexes:
			suffix_indexes[ch] = [i]
		else:
			suffix_indexes[ch].append(i)
	return suffix_indexes

def get_suffixes(word, suffix_indexes):
	suffixes = [word[idx:] for idx in suffix_indexes]
	return suffixes

def find_kth_char(word, k):
	suffix_indexes = make_suffix_dict(word)
	for letter in ALPHABET:
		if letter in suffix_indexes:
			suffixes = get_suffixes(word, suffix_indexes[letter])
			(ch, k) = substring_from_list(suffixes, k)
			if ch:
				return ch
test_cases = int(input())
for i in range(0, test_cases):
	line = input()
	k = int(input()) - 1
	print(find_kth_char(line, k))


import sys

def rendez(s, slen, l, l_first, l_last, diffstart):
	if l_first >= l_last:
		return
	diffstart1 = diffstart
	while True:
		sm_ord_min = ord('z') + 1
		sm_ord_max = ord('a') - 2
		for l_i in range(l_first, l_last + 1):
			sm_ord = ord(s[l[l_i] + diffstart1]) if l[l_i] + diffstart1 < slen else ord('a') - 1
			if sm_ord < sm_ord_min:
				sm_ord_min = sm_ord
			if sm_ord > sm_ord_max:
				sm_ord_max = sm_ord
		if sm_ord_min == sm_ord_max:
			diffstart1 += 1
		else:
			break
	sm = chr(int((sm_ord_min + sm_ord_max + 1) / 2))
	i1 = l_first
	i2 = l_last
	try:
		while i1 < i2:
			if l[i1] + diffstart1 == slen or s[l[i1] + diffstart1] < sm:
				i1 += 1
			elif l[i2] + diffstart1 < slen and s[l[i2] + diffstart1] >= sm:
				i2 -= 1
			else:
				ll = l[i1]
				l[i1] = l[i2]
				l[i2] = ll
				i1 += 1
	except:
		print((slen, l_first, l_last, i1, i2, l[i1], l[i2], diffstart, sm))
		return
	rendez(s, slen, l, l_first, i1 - 1, diffstart1)
	rendez(s, slen, l, i1, l_last, diffstart1)

def testcase(s, k):
	slenarray = [0] * (len(s) + 1)
	for i in range(1, len(s) + 1):
		slenarray[i] = slenarray[i - 1] + i
	l = list(range(len(s)))
	rendez(s, len(s), l, 0, len(l) - 1, 0)
	for i in range(len(s)):
		s0 = s[l[i - 1]:] if i > 0 else ''
		s1 = s[l[i]:]
		diffstart = 0
		while diffstart < len(s0) and diffstart < len(s1) and (s0[diffstart] == s1[diffstart]):
			diffstart = diffstart + 1
		slen = slenarray[len(s1)] - slenarray[diffstart]
		if k <= slen:
			d = diffstart + 1
			while k > 0:
				if k <= d:
					print(s1[k - 1])
					k = 0
					break
				else:
					k = k - d
					d = d + 1
		else:
			k = k - slen
		if k == 0:
			break
testcount = int(sys.stdin.readline())
for i in range(testcount):
	s = sys.stdin.readline()[:-1]
	k = int(sys.stdin.readline())
	testcase(s, k)


def suffix_array(text):
	keys = list(text)
	n = len(keys)
	s = sorted(range(n), key=keys.__getitem__)
	r = [0] * n
	k = 1

	def key(idx):
		return
	while True:
		c = 0
		prev = keys[s[0]]
		for idx in s:
			curr = keys[idx]
			if curr != prev:
				c = c + 1
			prev = curr
			r[idx] = c
		if c == n - 1:
			return (s, r)
		for idx in range(n):
			keys[idx] = (r[idx], r[idx + k] if idx + k < n else -1)
		s.sort(key=keys.__getitem__)
		k = 2 * k

def calculate_lcp(text, s, r):
	n = len(text)
	lcp = [0] * n
	v = 0
	for idx in r:
		if idx:
			curr = s[idx]
			prev = s[idx - 1]
			while prev + v < n and curr + v < n and (text[prev + v] == text[curr + v]):
				v = v + 1
			lcp[idx] = v
			if v:
				v = v - 1
	return lcp

def gauss(n):
	return n * (n + 1) // 2

def solve(text, k):
	n = len(text)
	(s, r) = suffix_array(text)
	lcp = calculate_lcp(text, s, r)
	for (idx, prefix) in zip(s, lcp):
		suf_len = n - idx
		batch_size = gauss(suf_len) - gauss(prefix)
		if k < batch_size:
			for word_len in range(prefix + 1, suf_len + 1):
				if k < word_len:
					return text[idx + k]
				else:
					k -= word_len
		k -= batch_size
t = int(input().strip())
for i in range(t):
	text = input().strip()
	k = int(input().strip()) - 1
	print(solve(text, k))


import os
import sys

def foo(text, k):
	stack = [('', list(range(len(text))))]
	while stack != []:
		(prefix, ii) = stack.pop()
		if k < len(prefix):
			return prefix[k]
		k -= len(prefix)
		cs = sorted([(text[i], i + 1) for i in ii if i < len(text)], reverse=True)
		i = 0
		while i < len(cs):
			c = cs[i][0]
			ii2 = [cs[i][1]]
			j = i + 1
			while j < len(cs) and cs[j][0] == c:
				ii2.append(cs[j][1])
				j += 1
			stack.append((prefix + c, ii2))
			i = j
	return None
T = int(input().strip())
for i in range(T):
	text = input().strip()
	k = int(input().strip())
	print(foo(text, k - 1))


import sys

def rendez(s, slen, l, l_first, l_last, diffstart):
	if l_first >= l_last:
		return
	diffstart1 = diffstart
	while True:
		sm_ord_min = ord('z') + 1
		sm_ord_max = ord('a') - 2
		for l_i in range(l_first, l_last + 1):
			sm_ord = ord(s[l[l_i] + diffstart1]) if l[l_i] + diffstart1 < slen else ord('a') - 1
			if sm_ord < sm_ord_min:
				sm_ord_min = sm_ord
			if sm_ord > sm_ord_max:
				sm_ord_max = sm_ord
		if sm_ord_min == sm_ord_max:
			diffstart1 += 1
		else:
			break
	sm = chr(int((sm_ord_min + sm_ord_max + 1) / 2))
	i1 = l_first
	i2 = l_last
	try:
		while i1 < i2:
			if l[i1] + diffstart1 == slen or s[l[i1] + diffstart1] < sm:
				i1 += 1
			elif l[i2] + diffstart1 < slen and s[l[i2] + diffstart1] >= sm:
				i2 -= 1
			else:
				ll = l[i1]
				l[i1] = l[i2]
				l[i2] = ll
				i1 += 1
	except:
		print((slen, l_first, l_last, i1, i2, l[i1], l[i2], diffstart, sm))
		return
	rendez(s, slen, l, l_first, i1 - 1, diffstart1)
	rendez(s, slen, l, i1, l_last, diffstart1)

def testcase(s, k):
	slenarray = [0] * (len(s) + 1)
	for i in range(1, len(s) + 1):
		slenarray[i] = slenarray[i - 1] + i
	l = list(range(len(s)))
	rendez(s, len(s), l, 0, len(l) - 1, 0)
	for i in range(len(s)):
		s0 = s[l[i - 1]:] if i > 0 else ''
		s1 = s[l[i]:]
		diffstart = 0
		while diffstart < len(s0) and diffstart < len(s1) and (s0[diffstart] == s1[diffstart]):
			diffstart = diffstart + 1
		slen = slenarray[len(s1)] - slenarray[diffstart]
		if k <= slen:
			d = diffstart + 1
			while k > 0:
				if k <= d:
					print(s1[k - 1])
					k = 0
					break
				else:
					k = k - d
					d = d + 1
		else:
			k = k - slen
		if k == 0:
			break
testcount = int(sys.stdin.readline())
for i in range(testcount):
	s = sys.stdin.readline()[:-1]
	k = int(sys.stdin.readline())
	testcase(s, k)


ALPHABET = 'abcdefghijklmnopqrstuvwxyz'

def do_it(base, k):
	base_len = len(base)
	counter = 0
	for letter in ALPHABET:
		sorted_i = [i for i in range(base_len) if base[i] == letter]
		sorted_i.sort(key=lambda x: base[x:])
		prev = None
		for index in sorted_i:
			start = 0
			if prev != None:
				while max(index + start, prev + start) < base_len and base[index + start] == base[prev + start]:
					start += 1
			for length in range(start + 1, base_len - index + 1):
				if counter + length > k:
					return base[index + k - counter]
				counter += length
			prev = index
n = int(input())
for _ in range(n):
	base = input()
	k = int(input()) - 1
	print(do_it(base, k))


from bisect import bisect_right
from itertools import zip_longest, islice

def T(n):
	return n * (n + 1) // 2

def sorted_idx(items):
	unique = sorted(set(items))
	idx = dict(zip(unique, range(len(unique))))
	return [idx[v] for v in items]

def suffix_array(s):
	n = len(s)
	k = 1
	sa = sorted_idx(s)
	while max(sa) < n - 1:
		sa = sorted_idx([a * (n + 1) + b + 1 for (a, b) in zip_longest(sa, islice(sa, k, None), fillvalue=-1)])
		k <<= 1
	return sa

def lcp_sa(s):
	inv_sa = suffix_array(s)
	n = len(inv_sa)
	sa = [0] * n
	for i in range(n):
		sa[inv_sa[i]] = i
	lcp = [0] * n
	k = 0
	for i in range(n):
		if inv_sa[i] == n - 1:
			k = 0
			continue
		j = sa[inv_sa[i] + 1]
		while i + k < n and j + k < n and (s[i + k] == s[j + k]):
			k += 1
		lcp[inv_sa[i] + 1] = k
		if k > 0:
			k -= 1
	return (sa, lcp)

def solve(s, K):
	n = len(s)
	(sa, lcp) = lcp_sa(s)
	F = 0
	for i in range(n):
		to_add = T(n - sa[i]) - T(lcp[i])
		if F + to_add >= K:
			break
		F += to_add
	K -= F
	F = 0
	for j in range(lcp[i], n):
		lim = T(j) - T(lcp[i])
		if K <= lim:
			break
		F = lim
	K -= F
	return s[sa[i] + K - 1]
q = int(input().strip())
for _ in range(q):
	string = input().strip()
	K = int(input().strip())
	print(solve(string, K))


import sys

def rendez(s, slen, l, l_first, l_last, diffstart):
	if l_first >= l_last:
		return
	diffstart1 = diffstart
	while True:
		sm_ord_min = ord('z') + 1
		sm_ord_max = ord('a') - 2
		for l_i in range(l_first, l_last + 1):
			sm_ord = ord(s[l[l_i] + diffstart1]) if l[l_i] + diffstart1 < slen else ord('a') - 1
			if sm_ord < sm_ord_min:
				sm_ord_min = sm_ord
			if sm_ord > sm_ord_max:
				sm_ord_max = sm_ord
		if sm_ord_min == sm_ord_max:
			diffstart1 += 1
		else:
			break
	sm = chr(int((sm_ord_min + sm_ord_max + 1) / 2))
	i1 = l_first
	i2 = l_last
	try:
		while i1 < i2:
			if l[i1] + diffstart1 == slen or s[l[i1] + diffstart1] < sm:
				i1 += 1
			elif l[i2] + diffstart1 < slen and s[l[i2] + diffstart1] >= sm:
				i2 -= 1
			else:
				ll = l[i1]
				l[i1] = l[i2]
				l[i2] = ll
				i1 += 1
	except:
		print((slen, l_first, l_last, i1, i2, l[i1], l[i2], diffstart, sm))
		return
	rendez(s, slen, l, l_first, i1 - 1, diffstart1)
	rendez(s, slen, l, i1, l_last, diffstart1)

def testcase(s, k):
	slenarray = [0] * (len(s) + 1)
	for i in range(1, len(s) + 1):
		slenarray[i] = slenarray[i - 1] + i
	l = list(range(len(s)))
	rendez(s, len(s), l, 0, len(l) - 1, 0)
	for i in range(len(s)):
		s0 = s[l[i - 1]:] if i > 0 else ''
		s1 = s[l[i]:]
		diffstart = 0
		while diffstart < len(s0) and diffstart < len(s1) and (s0[diffstart] == s1[diffstart]):
			diffstart = diffstart + 1
		slen = slenarray[len(s1)] - slenarray[diffstart]
		if k <= slen:
			d = diffstart + 1
			while k > 0:
				if k <= d:
					print(s1[k - 1])
					k = 0
					break
				else:
					k = k - d
					d = d + 1
		else:
			k = k - slen
		if k == 0:
			break
testcount = int(sys.stdin.readline())
for i in range(testcount):
	s = sys.stdin.readline()[:-1]
	k = int(sys.stdin.readline())
	testcase(s, k)


import sys

def rendez(s, slen, l, l_first, l_last, diffstart):
	if l_first >= l_last:
		return
	diffstart1 = diffstart
	while True:
		sm_ord_min = ord('z') + 1
		sm_ord_max = ord('a') - 2
		for l_i in range(l_first, l_last + 1):
			sm_ord = ord(s[l[l_i] + diffstart1]) if l[l_i] + diffstart1 < slen else ord('a') - 1
			if sm_ord < sm_ord_min:
				sm_ord_min = sm_ord
			if sm_ord > sm_ord_max:
				sm_ord_max = sm_ord
		if sm_ord_min == sm_ord_max:
			diffstart1 += 1
		else:
			break
	sm = chr(int((sm_ord_min + sm_ord_max + 1) / 2))
	i1 = l_first
	i2 = l_last
	try:
		while i1 < i2:
			if l[i1] + diffstart1 == slen or s[l[i1] + diffstart1] < sm:
				i1 += 1
			elif l[i2] + diffstart1 < slen and s[l[i2] + diffstart1] >= sm:
				i2 -= 1
			else:
				ll = l[i1]
				l[i1] = l[i2]
				l[i2] = ll
				i1 += 1
	except:
		print((slen, l_first, l_last, i1, i2, l[i1], l[i2], diffstart, sm))
		return
	rendez(s, slen, l, l_first, i1 - 1, diffstart1)
	rendez(s, slen, l, i1, l_last, diffstart1)

def testcase(s, k):
	slenarray = [0] * (len(s) + 1)
	for i in range(1, len(s) + 1):
		slenarray[i] = slenarray[i - 1] + i
	l = list(range(len(s)))
	rendez(s, len(s), l, 0, len(l) - 1, 0)
	for i in range(len(s)):
		s0 = s[l[i - 1]:] if i > 0 else ''
		s1 = s[l[i]:]
		diffstart = 0
		while diffstart < len(s0) and diffstart < len(s1) and (s0[diffstart] == s1[diffstart]):
			diffstart = diffstart + 1
		slen = slenarray[len(s1)] - slenarray[diffstart]
		if k <= slen:
			d = diffstart + 1
			while k > 0:
				if k <= d:
					print(s1[k - 1])
					k = 0
					break
				else:
					k = k - d
					d = d + 1
		else:
			k = k - slen
		if k == 0:
			break
testcount = int(sys.stdin.readline())
for i in range(testcount):
	s = sys.stdin.readline()[:-1]
	k = int(sys.stdin.readline())
	testcase(s, k)


import sys

def rendez(s, slen, l, l_first, l_last, diffstart):
	if l_first >= l_last:
		return
	diffstart1 = diffstart
	while True:
		sm_ord_min = ord('z') + 1
		sm_ord_max = ord('a') - 2
		for l_i in range(l_first, l_last + 1):
			sm_ord = ord(s[l[l_i] + diffstart1]) if l[l_i] + diffstart1 < slen else ord('a') - 1
			if sm_ord < sm_ord_min:
				sm_ord_min = sm_ord
			if sm_ord > sm_ord_max:
				sm_ord_max = sm_ord
		if sm_ord_min == sm_ord_max:
			diffstart1 += 1
		else:
			break
	sm = chr(int((sm_ord_min + sm_ord_max + 1) / 2))
	i1 = l_first
	i2 = l_last
	try:
		while i1 < i2:
			if l[i1] + diffstart1 == slen or s[l[i1] + diffstart1] < sm:
				i1 += 1
			elif l[i2] + diffstart1 < slen and s[l[i2] + diffstart1] >= sm:
				i2 -= 1
			else:
				ll = l[i1]
				l[i1] = l[i2]
				l[i2] = ll
				i1 += 1
	except:
		print((slen, l_first, l_last, i1, i2, l[i1], l[i2], diffstart, sm))
		return
	rendez(s, slen, l, l_first, i1 - 1, diffstart1)
	rendez(s, slen, l, i1, l_last, diffstart1)

def testcase(s, k):
	slenarray = [0] * (len(s) + 1)
	for i in range(1, len(s) + 1):
		slenarray[i] = slenarray[i - 1] + i
	l = list(range(len(s)))
	rendez(s, len(s), l, 0, len(l) - 1, 0)
	for i in range(len(s)):
		s0 = s[l[i - 1]:] if i > 0 else ''
		s1 = s[l[i]:]
		diffstart = 0
		while diffstart < len(s0) and diffstart < len(s1) and (s0[diffstart] == s1[diffstart]):
			diffstart = diffstart + 1
		slen = slenarray[len(s1)] - slenarray[diffstart]
		if k <= slen:
			d = diffstart + 1
			while k > 0:
				if k <= d:
					print(s1[k - 1])
					k = 0
					break
				else:
					k = k - d
					d = d + 1
		else:
			k = k - slen
		if k == 0:
			break
testcount = int(sys.stdin.readline())
for i in range(testcount):
	s = sys.stdin.readline()[:-1]
	k = int(sys.stdin.readline())
	testcase(s, k)


import sys

def rendez(s, slen, l, l_first, l_last, diffstart):
	if l_first >= l_last:
		return
	diffstart1 = diffstart
	while True:
		sm_ord_min = ord('z') + 1
		sm_ord_max = ord('a') - 2
		for l_i in range(l_first, l_last + 1):
			sm_ord = ord(s[l[l_i] + diffstart1]) if l[l_i] + diffstart1 < slen else ord('a') - 1
			if sm_ord < sm_ord_min:
				sm_ord_min = sm_ord
			if sm_ord > sm_ord_max:
				sm_ord_max = sm_ord
		if sm_ord_min == sm_ord_max:
			diffstart1 += 1
		else:
			break
	sm = chr(int((sm_ord_min + sm_ord_max + 1) / 2))
	i1 = l_first
	i2 = l_last
	try:
		while i1 < i2:
			if l[i1] + diffstart1 == slen or s[l[i1] + diffstart1] < sm:
				i1 += 1
			elif l[i2] + diffstart1 < slen and s[l[i2] + diffstart1] >= sm:
				i2 -= 1
			else:
				ll = l[i1]
				l[i1] = l[i2]
				l[i2] = ll
				i1 += 1
	except:
		print((slen, l_first, l_last, i1, i2, l[i1], l[i2], diffstart, sm))
		return
	rendez(s, slen, l, l_first, i1 - 1, diffstart1)
	rendez(s, slen, l, i1, l_last, diffstart1)

def testcase(s, k):
	slenarray = [0] * (len(s) + 1)
	for i in range(1, len(s) + 1):
		slenarray[i] = slenarray[i - 1] + i
	l = list(range(len(s)))
	rendez(s, len(s), l, 0, len(l) - 1, 0)
	for i in range(len(s)):
		s0 = s[l[i - 1]:] if i > 0 else ''
		s1 = s[l[i]:]
		diffstart = 0
		while diffstart < len(s0) and diffstart < len(s1) and (s0[diffstart] == s1[diffstart]):
			diffstart = diffstart + 1
		slen = slenarray[len(s1)] - slenarray[diffstart]
		if k <= slen:
			d = diffstart + 1
			while k > 0:
				if k <= d:
					print(s1[k - 1])
					k = 0
					break
				else:
					k = k - d
					d = d + 1
		else:
			k = k - slen
		if k == 0:
			break
testcount = int(sys.stdin.readline())
for i in range(testcount):
	s = sys.stdin.readline()[:-1]
	k = int(sys.stdin.readline())
	testcase(s, k)


import sys

def rendez(s, slen, l, l_first, l_last, diffstart):
	if l_first >= l_last:
		return
	diffstart1 = diffstart
	while True:
		sm_ord_min = ord('z') + 1
		sm_ord_max = ord('a') - 2
		for l_i in range(l_first, l_last + 1):
			sm_ord = ord(s[l[l_i] + diffstart1]) if l[l_i] + diffstart1 < slen else ord('a') - 1
			if sm_ord < sm_ord_min:
				sm_ord_min = sm_ord
			if sm_ord > sm_ord_max:
				sm_ord_max = sm_ord
		if sm_ord_min == sm_ord_max:
			diffstart1 += 1
		else:
			break
	sm = chr(int((sm_ord_min + sm_ord_max + 1) / 2))
	i1 = l_first
	i2 = l_last
	try:
		while i1 < i2:
			if l[i1] + diffstart1 == slen or s[l[i1] + diffstart1] < sm:
				i1 += 1
			elif l[i2] + diffstart1 < slen and s[l[i2] + diffstart1] >= sm:
				i2 -= 1
			else:
				ll = l[i1]
				l[i1] = l[i2]
				l[i2] = ll
				i1 += 1
	except:
		print((slen, l_first, l_last, i1, i2, l[i1], l[i2], diffstart, sm))
		return
	rendez(s, slen, l, l_first, i1 - 1, diffstart1)
	rendez(s, slen, l, i1, l_last, diffstart1)

def testcase(s, k):
	slenarray = [0] * (len(s) + 1)
	for i in range(1, len(s) + 1):
		slenarray[i] = slenarray[i - 1] + i
	l = list(range(len(s)))
	rendez(s, len(s), l, 0, len(l) - 1, 0)
	for i in range(len(s)):
		s0 = s[l[i - 1]:] if i > 0 else ''
		s1 = s[l[i]:]
		diffstart = 0
		while diffstart < len(s0) and diffstart < len(s1) and (s0[diffstart] == s1[diffstart]):
			diffstart = diffstart + 1
		slen = slenarray[len(s1)] - slenarray[diffstart]
		if k <= slen:
			d = diffstart + 1
			while k > 0:
				if k <= d:
					print(s1[k - 1])
					k = 0
					break
				else:
					k = k - d
					d = d + 1
		else:
			k = k - slen
		if k == 0:
			break
testcount = int(sys.stdin.readline())
for i in range(testcount):
	s = sys.stdin.readline()[:-1]
	k = int(sys.stdin.readline())
	testcase(s, k)


import sys

def rendez(s, slen, l, l_first, l_last, diffstart):
	if l_first >= l_last:
		return
	diffstart1 = diffstart
	while True:
		sm_ord_min = ord('z') + 1
		sm_ord_max = ord('a') - 2
		for l_i in range(l_first, l_last + 1):
			sm_ord = ord(s[l[l_i] + diffstart1]) if l[l_i] + diffstart1 < slen else ord('a') - 1
			if sm_ord < sm_ord_min:
				sm_ord_min = sm_ord
			if sm_ord > sm_ord_max:
				sm_ord_max = sm_ord
		if sm_ord_min == sm_ord_max:
			diffstart1 += 1
		else:
			break
	sm = chr(int((sm_ord_min + sm_ord_max + 1) / 2))
	i1 = l_first
	i2 = l_last
	try:
		while i1 < i2:
			if l[i1] + diffstart1 == slen or s[l[i1] + diffstart1] < sm:
				i1 += 1
			elif l[i2] + diffstart1 < slen and s[l[i2] + diffstart1] >= sm:
				i2 -= 1
			else:
				ll = l[i1]
				l[i1] = l[i2]
				l[i2] = ll
				i1 += 1
	except:
		print((slen, l_first, l_last, i1, i2, l[i1], l[i2], diffstart, sm))
		return
	rendez(s, slen, l, l_first, i1 - 1, diffstart1)
	rendez(s, slen, l, i1, l_last, diffstart1)

def testcase(s, k):
	slenarray = [0] * (len(s) + 1)
	for i in range(1, len(s) + 1):
		slenarray[i] = slenarray[i - 1] + i
	l = list(range(len(s)))
	rendez(s, len(s), l, 0, len(l) - 1, 0)
	for i in range(len(s)):
		s0 = s[l[i - 1]:] if i > 0 else ''
		s1 = s[l[i]:]
		diffstart = 0
		while diffstart < len(s0) and diffstart < len(s1) and (s0[diffstart] == s1[diffstart]):
			diffstart = diffstart + 1
		slen = slenarray[len(s1)] - slenarray[diffstart]
		if k <= slen:
			d = diffstart + 1
			while k > 0:
				if k <= d:
					print(s1[k - 1])
					k = 0
					break
				else:
					k = k - d
					d = d + 1
		else:
			k = k - slen
		if k == 0:
			break
testcount = int(sys.stdin.readline())
for i in range(testcount):
	s = sys.stdin.readline()[:-1]
	k = int(sys.stdin.readline())
	testcase(s, k)


import sys

def rendez(s, slen, l, l_first, l_last, diffstart):
	if l_first >= l_last:
		return
	diffstart1 = diffstart
	while True:
		sm_ord_min = ord('z') + 1
		sm_ord_max = ord('a') - 2
		for l_i in range(l_first, l_last + 1):
			sm_ord = ord(s[l[l_i] + diffstart1]) if l[l_i] + diffstart1 < slen else ord('a') - 1
			if sm_ord < sm_ord_min:
				sm_ord_min = sm_ord
			if sm_ord > sm_ord_max:
				sm_ord_max = sm_ord
		if sm_ord_min == sm_ord_max:
			diffstart1 += 1
		else:
			break
	sm = chr(int((sm_ord_min + sm_ord_max + 1) / 2))
	i1 = l_first
	i2 = l_last
	try:
		while i1 < i2:
			if l[i1] + diffstart1 == slen or s[l[i1] + diffstart1] < sm:
				i1 += 1
			elif l[i2] + diffstart1 < slen and s[l[i2] + diffstart1] >= sm:
				i2 -= 1
			else:
				ll = l[i1]
				l[i1] = l[i2]
				l[i2] = ll
				i1 += 1
	except:
		print((slen, l_first, l_last, i1, i2, l[i1], l[i2], diffstart, sm))
		return
	rendez(s, slen, l, l_first, i1 - 1, diffstart1)
	rendez(s, slen, l, i1, l_last, diffstart1)

def testcase(s, k):
	slenarray = [0] * (len(s) + 1)
	for i in range(1, len(s) + 1):
		slenarray[i] = slenarray[i - 1] + i
	l = list(range(len(s)))
	rendez(s, len(s), l, 0, len(l) - 1, 0)
	for i in range(len(s)):
		s0 = s[l[i - 1]:] if i > 0 else ''
		s1 = s[l[i]:]
		diffstart = 0
		while diffstart < len(s0) and diffstart < len(s1) and (s0[diffstart] == s1[diffstart]):
			diffstart = diffstart + 1
		slen = slenarray[len(s1)] - slenarray[diffstart]
		if k <= slen:
			d = diffstart + 1
			while k > 0:
				if k <= d:
					print(s1[k - 1])
					k = 0
					break
				else:
					k = k - d
					d = d + 1
		else:
			k = k - slen
		if k == 0:
			break
testcount = int(sys.stdin.readline())
for i in range(testcount):
	s = sys.stdin.readline()[:-1]
	k = int(sys.stdin.readline())
	testcase(s, k)


def substring_from_index(string, idx):
	for i in range(idx + 1, len(string) + 1):
		yield string[:i]
	return

def substring_from_list(suffixes, k):
	suffixes.sort()
	substrs = ''
	last_suffix = ''
	for suffix in suffixes:
		idx = 0
		if last_suffix != '':
			idx = 1
			while idx < len(suffix) and idx < len(last_suffix) and (last_suffix[idx] == suffix[idx]):
				idx = idx + 1
		for substr in substring_from_index(suffix, idx):
			if len(substr) < k:
				k = k - len(substr)
			else:
				return (substr[k], k)
		last_suffix = suffix
	return (None, k)
ALPHABET = ['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']

def make_suffix_dict(word):
	suffix_indexes = dict()
	for (i, ch) in enumerate(word):
		if ch not in suffix_indexes:
			suffix_indexes[ch] = [i]
		else:
			suffix_indexes[ch].append(i)
	return suffix_indexes

def get_suffixes(word, suffix_indexes):
	suffixes = [word[idx:] for idx in suffix_indexes]
	return suffixes

def find_kth_char(word, k):
	suffix_indexes = make_suffix_dict(word)
	for letter in ALPHABET:
		if letter in suffix_indexes:
			suffixes = get_suffixes(word, suffix_indexes[letter])
			(ch, k) = substring_from_list(suffixes, k)
			if ch:
				return ch
test_cases = int(input())
for i in range(0, test_cases):
	line = input()
	k = int(input()) - 1
	print(find_kth_char(line, k))


ALPHABET = 'abcdefghijklmnopqrstuvwxyz'

def ashtonString(base, k):
	base_len = len(base)
	counter = 0
	for letter in ALPHABET:
		sorted_i = [i for i in range(base_len) if base[i] == letter]
		sorted_i.sort(key=lambda x: base[x:])
		prev = None
		for index in sorted_i:
			start = 0
			if prev != None:
				while max(index + start, prev + start) < base_len and base[index + start] == base[prev + start]:
					start += 1
			for length in range(start + 1, base_len - index + 1):
				if counter + length > k:
					return base[index + k - counter]
				counter += length
			prev = index
n = int(input())
for _ in range(n):
	base = input()
	k = int(input()) - 1
	print(ashtonString(base, k))


def foo(text, k):
	stack = [('', list(range(len(text))))]
	while stack != []:
		(prefix, ii) = stack.pop()
		if k < len(prefix):
			return prefix[k]
		k -= len(prefix)
		cs = sorted([(text[i], i + 1) for i in ii if i < len(text)], reverse=True)
		i = 0
		while i < len(cs):
			c = cs[i][0]
			ii2 = [cs[i][1]]
			j = i + 1
			while j < len(cs) and cs[j][0] == c:
				ii2.append(cs[j][1])
				j += 1
			stack.append((prefix + c, ii2))
			i = j
	return None
T = int(input().strip())
for i in range(T):
	text = input().strip()
	k = int(input().strip())
	print(foo(text, k - 1))


def foo(text, k):
	stack = [('', list(range(len(text))))]
	while stack != []:
		(prefix, ii) = stack.pop()
		if k < len(prefix):
			return prefix[k]
		k -= len(prefix)
		cs = sorted([(text[i], i + 1) for i in ii if i < len(text)], reverse=True)
		i = 0
		while i < len(cs):
			c = cs[i][0]
			ii2 = [cs[i][1]]
			j = i + 1
			while j < len(cs) and cs[j][0] == c:
				ii2.append(cs[j][1])
				j += 1
			stack.append((prefix + c, ii2))
			i = j
	return None
T = int(input().strip())
for i in range(T):
	text = input().strip()
	k = int(input().strip())
	print(foo(text, k - 1))


ALPHABET = 'abcdefghijklmnopqrstuvwxyz'

def do_it(base, k):
	base_len = len(base)
	counter = 0
	for letter in ALPHABET:
		sorted_i = [i for i in range(base_len) if base[i] == letter]
		sorted_i.sort(key=lambda x: base[x:])
		prev = None
		for index in sorted_i:
			start = 0
			if prev != None:
				while max(index + start, prev + start) < base_len and base[index + start] == base[prev + start]:
					start += 1
			for length in range(start + 1, base_len - index + 1):
				if counter + length > k:
					return base[index + k - counter]
				counter += length
			prev = index
n = int(input())
for _ in range(n):
	base = input()
	k = int(input()) - 1
	print(do_it(base, k))


def find_all(s, c):
	p = -1
	while True:
		p = s.find(c, p + 1)
		if p < 0:
			break
		yield p

def xxx(s, k):
	k -= 1
	slength = len(s)
	queue = [(list(find_all(s, char)), 1) for char in sorted(list(set(s)), reverse=True)]
	while len(queue) > 0:
		(starts, length) = queue.pop()
		if k < length:
			substring = s[starts[0]:starts[0] + length]
			return substring[k]
		k -= length
		nextdict = {}
		for start in starts:
			if start + length < slength:
				nextdict.setdefault(s[start + length], []).append(start)
		for char in sorted(nextdict, reverse=True):
			queue.append((nextdict[char], length + 1))
t = int(input())
for _ in range(t):
	s = input()
	k = int(input())
	print(xxx(s, k))


def foo(text, k):
	stack = [('', list(range(len(text))))]
	while stack != []:
		(prefix, ii) = stack.pop()
		if k < len(prefix):
			return prefix[k]
		k -= len(prefix)
		cs = sorted([(text[i], i + 1) for i in ii if i < len(text)], reverse=True)
		i = 0
		while i < len(cs):
			c = cs[i][0]
			ii2 = [cs[i][1]]
			j = i + 1
			while j < len(cs) and cs[j][0] == c:
				ii2.append(cs[j][1])
				j += 1
			stack.append((prefix + c, ii2))
			i = j
	return None
T = int(input().strip())
for i in range(T):
	text = input().strip()
	k = int(input().strip())
	print(foo(text, k - 1))


import itertools
t = int(input())
alphabets = 'abcdefghijklmnopqrstuvwxyz'
for a in range(t):
	s = input()
	k = int(input())
	out = ''
	count = 0
	for letter in alphabets:
		subs = []
		lst_index = [pos for (pos, char) in enumerate(s) if char == letter]
		if len(lst_index) < 1:
			continue
		for i in lst_index:
			subs.append(s[i:])
		del lst_index
		subs.sort()
		for i in range(len(subs)):
			sub = subs[i]
			for j in range(len(sub)):
				suff = sub[:j + 1]
				dupl = False
				for r in range(i):
					if subs[r].find(suff) == 0:
						dupl = True
						break
				if dupl:
					continue
				count += len(suff)
				if count >= k:
					print(suff[len(suff) + (k - count) - 1])
					break
			if count >= k:
				break
		if count >= k:
			break


def substring_from_index(string, idx):
	for i in range(idx + 1, len(string) + 1):
		yield string[:i]
	return

def substring_from_list(suffixes, k):
	suffixes.sort()
	substrs = ''
	last_suffix = ''
	for suffix in suffixes:
		if suffix == last_suffix:
			continue
		idx = 0
		if last_suffix != '':
			idx = 1
			while idx < len(suffix) and idx < len(last_suffix) and (last_suffix[idx] == suffix[idx]):
				idx = idx + 1
		for substr in substring_from_index(suffix, idx):
			if len(substr) < k:
				k = k - len(substr)
			else:
				return (substr[k], k)
		last_suffix = suffix
	return (None, k)
ALPHABET = ['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']

def make_suffix_dict(word):
	suffix_indexes = dict()
	for (i, ch) in enumerate(word):
		if ch not in suffix_indexes:
			suffix_indexes[ch] = [i]
		else:
			suffix_indexes[ch].append(i)
	return suffix_indexes

def get_suffixes(word, suffix_indexes):
	suffixes = [word[idx:] for idx in suffix_indexes]
	return suffixes

def find_kth_char(word, k):
	suffix_indexes = make_suffix_dict(word)
	for letter in ALPHABET:
		if letter in suffix_indexes:
			suffixes = get_suffixes(word, suffix_indexes[letter])
			(ch, k) = substring_from_list(suffixes, k)
			if ch:
				return ch
test_cases = int(input())
for i in range(0, test_cases):
	line = input()
	k = int(input()) - 1
	print(find_kth_char(line, k))


import sys

def rendez(s, slen, l, l_first, l_last, diffstart):
	if l_first >= l_last:
		return
	diffstart1 = diffstart
	while True:
		sm_ord_min = ord('z') + 1
		sm_ord_max = ord('a') - 2
		for l_i in range(l_first, l_last + 1):
			sm_ord = ord(s[l[l_i] + diffstart1]) if l[l_i] + diffstart1 < slen else ord('a') - 1
			if sm_ord < sm_ord_min:
				sm_ord_min = sm_ord
			if sm_ord > sm_ord_max:
				sm_ord_max = sm_ord
		if sm_ord_min == sm_ord_max:
			diffstart1 += 1
		else:
			break
	sm = chr(int((sm_ord_min + sm_ord_max + 1) / 2))
	i1 = l_first
	i2 = l_last
	try:
		while i1 < i2:
			if l[i1] + diffstart1 == slen or s[l[i1] + diffstart1] < sm:
				i1 += 1
			elif l[i2] + diffstart1 < slen and s[l[i2] + diffstart1] >= sm:
				i2 -= 1
			else:
				ll = l[i1]
				l[i1] = l[i2]
				l[i2] = ll
				i1 += 1
	except:
		print((slen, l_first, l_last, i1, i2, l[i1], l[i2], diffstart, sm))
		return
	rendez(s, slen, l, l_first, i1 - 1, diffstart1)
	rendez(s, slen, l, i1, l_last, diffstart1)

def testcase(s, k):
	slenarray = [0] * (len(s) + 1)
	for i in range(1, len(s) + 1):
		slenarray[i] = slenarray[i - 1] + i
	l = list(range(len(s)))
	rendez(s, len(s), l, 0, len(l) - 1, 0)
	for i in range(len(s)):
		s0 = s[l[i - 1]:] if i > 0 else ''
		s1 = s[l[i]:]
		diffstart = 0
		while diffstart < len(s0) and diffstart < len(s1) and (s0[diffstart] == s1[diffstart]):
			diffstart = diffstart + 1
		slen = slenarray[len(s1)] - slenarray[diffstart]
		if k <= slen:
			d = diffstart + 1
			while k > 0:
				if k <= d:
					print(s1[k - 1])
					k = 0
					break
				else:
					k = k - d
					d = d + 1
		else:
			k = k - slen
		if k == 0:
			break
testcount = int(sys.stdin.readline())
for i in range(testcount):
	s = sys.stdin.readline()[:-1]
	k = int(sys.stdin.readline())
	testcase(s, k)


def foo(text, k):
	stack = [('', list(range(len(text))))]
	while stack != []:
		(prefix, ii) = stack.pop()
		if k < len(prefix):
			return prefix[k]
		k -= len(prefix)
		cs = sorted([(text[i], i + 1) for i in ii if i < len(text)], reverse=True)
		i = 0
		while i < len(cs):
			c = cs[i][0]
			ii2 = [cs[i][1]]
			j = i + 1
			while j < len(cs) and cs[j][0] == c:
				ii2.append(cs[j][1])
				j += 1
			stack.append((prefix + c, ii2))
			i = j
	return None
T = int(input().strip())
for i in range(T):
	text = input().strip()
	k = int(input().strip())
	print(foo(text, k - 1))


ALPHABET = 'abcdefghijklmnopqrstuvwxyz'

def do_it(base, k):
	base_len = len(base)
	counter = 0
	for letter in ALPHABET:
		sorted_i = [i for i in range(base_len) if base[i] == letter]
		sorted_i.sort(key=lambda x: base[x:])
		prev = None
		for index in sorted_i:
			start = 0
			if prev != None:
				while max(index + start, prev + start) < base_len and base[index + start] == base[prev + start]:
					start += 1
			for length in range(start + 1, base_len - index + 1):
				if counter + length > k:
					return base[index + k - counter]
				counter += length
			prev = index
n = int(input())
for _ in range(n):
	base = input()
	k = int(input()) - 1
	print(do_it(base, k))


import sys

def rendez(s, slen, l, l_first, l_last, diffstart):
	if l_first >= l_last:
		return
	diffstart1 = diffstart
	while True:
		sm_ord_min = ord('z') + 1
		sm_ord_max = ord('a') - 2
		for l_i in range(l_first, l_last + 1):
			sm_ord = ord(s[l[l_i] + diffstart1]) if l[l_i] + diffstart1 < slen else ord('a') - 1
			if sm_ord < sm_ord_min:
				sm_ord_min = sm_ord
			if sm_ord > sm_ord_max:
				sm_ord_max = sm_ord
		if sm_ord_min == sm_ord_max:
			diffstart1 += 1
		else:
			break
	sm = chr(int((sm_ord_min + sm_ord_max + 1) / 2))
	i1 = l_first
	i2 = l_last
	try:
		while i1 < i2:
			if l[i1] + diffstart1 == slen or s[l[i1] + diffstart1] < sm:
				i1 += 1
			elif l[i2] + diffstart1 < slen and s[l[i2] + diffstart1] >= sm:
				i2 -= 1
			else:
				ll = l[i1]
				l[i1] = l[i2]
				l[i2] = ll
				i1 += 1
	except:
		print((slen, l_first, l_last, i1, i2, l[i1], l[i2], diffstart, sm))
		return
	rendez(s, slen, l, l_first, i1 - 1, diffstart1)
	rendez(s, slen, l, i1, l_last, diffstart1)

def testcase(s, k):
	slenarray = [0] * (len(s) + 1)
	for i in range(1, len(s) + 1):
		slenarray[i] = slenarray[i - 1] + i
	l = list(range(len(s)))
	rendez(s, len(s), l, 0, len(l) - 1, 0)
	for i in range(len(s)):
		s0 = s[l[i - 1]:] if i > 0 else ''
		s1 = s[l[i]:]
		diffstart = 0
		while diffstart < len(s0) and diffstart < len(s1) and (s0[diffstart] == s1[diffstart]):
			diffstart = diffstart + 1
		slen = slenarray[len(s1)] - slenarray[diffstart]
		if k <= slen:
			d = diffstart + 1
			while k > 0:
				if k <= d:
					print(s1[k - 1])
					k = 0
					break
				else:
					k = k - d
					d = d + 1
		else:
			k = k - slen
		if k == 0:
			break
testcount = int(sys.stdin.readline())
for i in range(testcount):
	s = sys.stdin.readline()[:-1]
	k = int(sys.stdin.readline())
	testcase(s, k)


def solve(text, k):
	stack = [('', list(range(len(text))))]
	while stack:
		(prefix, it) = stack.pop()
		if k < len(prefix):
			return prefix[k]
		k -= len(prefix)
		cs = sorted([(text[i], i + 1) for i in it if i < len(text)], reverse=True)
		i = 0
		while i < len(cs):
			c = cs[i][0]
			ii2 = [cs[i][1]]
			j = i + 1
			while j < len(cs) and cs[j][0] == c:
				ii2.append(cs[j][1])
				j += 1
			stack.append((prefix + c, ii2))
			i = j
for i in range(int(input())):
	text = input()
	k = int(input())
	print(solve(text, k - 1))


ALBHABET = 'abcdefghijklmnopqrstuvwxyz'

def do_it(base, k):
	base_len = len(base)
	counter = 0
	for letter in ALBHABET:
		sorted_i = [i for i in range(base_len) if base[i] == letter]
		sorted_i.sort(key=lambda x: base[x:])
		prev = None
		for index in sorted_i:
			start = 0
			if prev != None:
				while max(index + start, prev + start) < base_len and base[index + start] == base[prev + start]:
					start += 1
			for length in range(start + 1, base_len - index + 1):
				if counter + length > k:
					return base[index + k - counter]
				counter += length
			prev = index
n = int(input())
for _ in range(n):
	base = input()
	k = int(input()) - 1
	print(do_it(base, k))


def foo(text, k):
	stack = [('', list(range(len(text))))]
	while stack != []:
		(prefix, ii) = stack.pop()
		if k < len(prefix):
			return prefix[k]
		k -= len(prefix)
		cs = sorted([(text[i], i + 1) for i in ii if i < len(text)], reverse=True)
		i = 0
		while i < len(cs):
			c = cs[i][0]
			ii2 = [cs[i][1]]
			j = i + 1
			while j < len(cs) and cs[j][0] == c:
				ii2.append(cs[j][1])
				j += 1
			stack.append((prefix + c, ii2))
			i = j
	return None
T = int(input().strip())
for i in range(T):
	text = input().strip()
	k = int(input().strip())
	print(foo(text, k - 1))


import sys

def rendez(s, slen, l, l_first, l_last, diffstart):
	if l_first >= l_last:
		return
	diffstart1 = diffstart
	while True:
		sm_ord_min = ord('z') + 1
		sm_ord_max = ord('a') - 2
		for l_i in range(l_first, l_last + 1):
			sm_ord = ord(s[l[l_i] + diffstart1]) if l[l_i] + diffstart1 < slen else ord('a') - 1
			if sm_ord < sm_ord_min:
				sm_ord_min = sm_ord
			if sm_ord > sm_ord_max:
				sm_ord_max = sm_ord
		if sm_ord_min == sm_ord_max:
			diffstart1 += 1
		else:
			break
	sm = chr(int((sm_ord_min + sm_ord_max + 1) / 2))
	i1 = l_first
	i2 = l_last
	try:
		while i1 < i2:
			if l[i1] + diffstart1 == slen or s[l[i1] + diffstart1] < sm:
				i1 += 1
			elif l[i2] + diffstart1 < slen and s[l[i2] + diffstart1] >= sm:
				i2 -= 1
			else:
				ll = l[i1]
				l[i1] = l[i2]
				l[i2] = ll
				i1 += 1
	except:
		print((slen, l_first, l_last, i1, i2, l[i1], l[i2], diffstart, sm))
		return
	rendez(s, slen, l, l_first, i1 - 1, diffstart1)
	rendez(s, slen, l, i1, l_last, diffstart1)

def testcase(s, k):
	slenarray = [0] * (len(s) + 1)
	for i in range(1, len(s) + 1):
		slenarray[i] = slenarray[i - 1] + i
	l = list(range(len(s)))
	rendez(s, len(s), l, 0, len(l) - 1, 0)
	for i in range(len(s)):
		s0 = s[l[i - 1]:] if i > 0 else ''
		s1 = s[l[i]:]
		diffstart = 0
		while diffstart < len(s0) and diffstart < len(s1) and (s0[diffstart] == s1[diffstart]):
			diffstart = diffstart + 1
		slen = slenarray[len(s1)] - slenarray[diffstart]
		if k <= slen:
			d = diffstart + 1
			while k > 0:
				if k <= d:
					print(s1[k - 1])
					k = 0
					break
				else:
					k = k - d
					d = d + 1
		else:
			k = k - slen
		if k == 0:
			break
testcount = int(sys.stdin.readline())
for i in range(testcount):
	s = sys.stdin.readline()[:-1]
	k = int(sys.stdin.readline())
	testcase(s, k)


import sys
from collections import defaultdict, Counter

def generate_suffixarray(thestr):
	d = defaultdict(list)
	for i in range(len(thestr)):
		d[thestr[i]].append(i)
	result = []
	for (k, v) in sorted(d.items()):
		if len(v) == 1:
			result.append(v[0])
		else:
			dd = defaultdict(list)
			for i in v:
				dd[thestr[i:]].append(i)
			for (k2, v2) in sorted(dd.items()):
				result.append(v2[0])
			del dd
	return result

def find_nth_char(thestr, k):
	sa = generate_suffixarray(thestr)
	prevsastr = ''
	for s in sa:
		cursastr = thestr[s:]
		offset = 1
		while prevsastr[0:offset] == cursastr[0:offset]:
			offset += 1
		for j in range(offset, len(cursastr) + 1):
			thesubstr = cursastr[0:j]
			lensubstr = len(thesubstr)
			if k > lensubstr:
				k -= lensubstr
			else:
				print(thesubstr[k - 1])
				return
		prevsastr = cursastr
cases = int(input().strip())
for _ in range(cases):
	givenstr = input().strip()
	k = int(input().strip())
	find_nth_char(givenstr, k)


import sys

def rendez(s, slen, l, l_first, l_last, diffstart):
	if l_first >= l_last:
		return
	diffstart1 = diffstart
	while True:
		sm_ord_min = ord('z') + 1
		sm_ord_max = ord('a') - 2
		for l_i in range(l_first, l_last + 1):
			sm_ord = ord(s[l[l_i] + diffstart1]) if l[l_i] + diffstart1 < slen else ord('a') - 1
			if sm_ord < sm_ord_min:
				sm_ord_min = sm_ord
			if sm_ord > sm_ord_max:
				sm_ord_max = sm_ord
		if sm_ord_min == sm_ord_max:
			diffstart1 += 1
		else:
			break
	sm = chr(int((sm_ord_min + sm_ord_max + 1) / 2))
	i1 = l_first
	i2 = l_last
	try:
		while i1 < i2:
			if l[i1] + diffstart1 == slen or s[l[i1] + diffstart1] < sm:
				i1 += 1
			elif l[i2] + diffstart1 < slen and s[l[i2] + diffstart1] >= sm:
				i2 -= 1
			else:
				ll = l[i1]
				l[i1] = l[i2]
				l[i2] = ll
				i1 += 1
	except:
		print((slen, l_first, l_last, i1, i2, l[i1], l[i2], diffstart, sm))
		return
	rendez(s, slen, l, l_first, i1 - 1, diffstart1)
	rendez(s, slen, l, i1, l_last, diffstart1)

def testcase(s, k):
	slenarray = [0] * (len(s) + 1)
	for i in range(1, len(s) + 1):
		slenarray[i] = slenarray[i - 1] + i
	l = list(range(len(s)))
	rendez(s, len(s), l, 0, len(l) - 1, 0)
	for i in range(len(s)):
		s0 = s[l[i - 1]:] if i > 0 else ''
		s1 = s[l[i]:]
		diffstart = 0
		while diffstart < len(s0) and diffstart < len(s1) and (s0[diffstart] == s1[diffstart]):
			diffstart = diffstart + 1
		slen = slenarray[len(s1)] - slenarray[diffstart]
		if k <= slen:
			d = diffstart + 1
			while k > 0:
				if k <= d:
					print(s1[k - 1])
					k = 0
					break
				else:
					k = k - d
					d = d + 1
		else:
			k = k - slen
		if k == 0:
			break
testcount = int(sys.stdin.readline())
for i in range(testcount):
	s = sys.stdin.readline()[:-1]
	k = int(sys.stdin.readline())
	testcase(s, k)


import sys

def rendez(s, slen, l, l_first, l_last, diffstart):
	if l_first >= l_last:
		return
	diffstart1 = diffstart
	while True:
		sm_ord_min = ord('z') + 1
		sm_ord_max = ord('a') - 2
		for l_i in range(l_first, l_last + 1):
			sm_ord = ord(s[l[l_i] + diffstart1]) if l[l_i] + diffstart1 < slen else ord('a') - 1
			if sm_ord < sm_ord_min:
				sm_ord_min = sm_ord
			if sm_ord > sm_ord_max:
				sm_ord_max = sm_ord
		if sm_ord_min == sm_ord_max:
			diffstart1 += 1
		else:
			break
	sm = chr(int((sm_ord_min + sm_ord_max + 1) / 2))
	i1 = l_first
	i2 = l_last
	try:
		while i1 < i2:
			if l[i1] + diffstart1 == slen or s[l[i1] + diffstart1] < sm:
				i1 += 1
			elif l[i2] + diffstart1 < slen and s[l[i2] + diffstart1] >= sm:
				i2 -= 1
			else:
				ll = l[i1]
				l[i1] = l[i2]
				l[i2] = ll
				i1 += 1
	except:
		print((slen, l_first, l_last, i1, i2, l[i1], l[i2], diffstart, sm))
		return
	rendez(s, slen, l, l_first, i1 - 1, diffstart1)
	rendez(s, slen, l, i1, l_last, diffstart1)

def testcase(s, k):
	slenarray = [0] * (len(s) + 1)
	for i in range(1, len(s) + 1):
		slenarray[i] = slenarray[i - 1] + i
	l = list(range(len(s)))
	rendez(s, len(s), l, 0, len(l) - 1, 0)
	for i in range(len(s)):
		s0 = s[l[i - 1]:] if i > 0 else ''
		s1 = s[l[i]:]
		diffstart = 0
		while diffstart < len(s0) and diffstart < len(s1) and (s0[diffstart] == s1[diffstart]):
			diffstart = diffstart + 1
		slen = slenarray[len(s1)] - slenarray[diffstart]
		if k <= slen:
			d = diffstart + 1
			while k > 0:
				if k <= d:
					print(s1[k - 1])
					k = 0
					break
				else:
					k = k - d
					d = d + 1
		else:
			k = k - slen
		if k == 0:
			break
testcount = int(sys.stdin.readline())
for i in range(testcount):
	s = sys.stdin.readline()[:-1]
	k = int(sys.stdin.readline())
	testcase(s, k)


import sys

def rendez(s, slen, l, l_first, l_last, diffstart):
	if l_first >= l_last:
		return
	diffstart1 = diffstart
	while True:
		sm_ord_min = ord('z') + 1
		sm_ord_max = ord('a') - 2
		for l_i in range(l_first, l_last + 1):
			sm_ord = ord(s[l[l_i] + diffstart1]) if l[l_i] + diffstart1 < slen else ord('a') - 1
			if sm_ord < sm_ord_min:
				sm_ord_min = sm_ord
			if sm_ord > sm_ord_max:
				sm_ord_max = sm_ord
		if sm_ord_min == sm_ord_max:
			diffstart1 += 1
		else:
			break
	sm = chr(int((sm_ord_min + sm_ord_max + 1) / 2))
	i1 = l_first
	i2 = l_last
	try:
		while i1 < i2:
			if l[i1] + diffstart1 == slen or s[l[i1] + diffstart1] < sm:
				i1 += 1
			elif l[i2] + diffstart1 < slen and s[l[i2] + diffstart1] >= sm:
				i2 -= 1
			else:
				ll = l[i1]
				l[i1] = l[i2]
				l[i2] = ll
				i1 += 1
	except:
		print((slen, l_first, l_last, i1, i2, l[i1], l[i2], diffstart, sm))
		return
	rendez(s, slen, l, l_first, i1 - 1, diffstart1)
	rendez(s, slen, l, i1, l_last, diffstart1)

def testcase(s, k):
	slenarray = [0] * (len(s) + 1)
	for i in range(1, len(s) + 1):
		slenarray[i] = slenarray[i - 1] + i
	l = list(range(len(s)))
	rendez(s, len(s), l, 0, len(l) - 1, 0)
	for i in range(len(s)):
		s0 = s[l[i - 1]:] if i > 0 else ''
		s1 = s[l[i]:]
		diffstart = 0
		while diffstart < len(s0) and diffstart < len(s1) and (s0[diffstart] == s1[diffstart]):
			diffstart = diffstart + 1
		slen = slenarray[len(s1)] - slenarray[diffstart]
		if k <= slen:
			d = diffstart + 1
			while k > 0:
				if k <= d:
					print(s1[k - 1])
					k = 0
					break
				else:
					k = k - d
					d = d + 1
		else:
			k = k - slen
		if k == 0:
			break
testcount = int(sys.stdin.readline())
for i in range(testcount):
	s = sys.stdin.readline()[:-1]
	k = int(sys.stdin.readline())
	testcase(s, k)


import sys

def rendez(s, slen, l, l_first, l_last, diffstart):
	if l_first >= l_last:
		return
	diffstart1 = diffstart
	while True:
		sm_ord_min = ord('z') + 1
		sm_ord_max = ord('a') - 2
		for l_i in range(l_first, l_last + 1):
			sm_ord = ord(s[l[l_i] + diffstart1]) if l[l_i] + diffstart1 < slen else ord('a') - 1
			if sm_ord < sm_ord_min:
				sm_ord_min = sm_ord
			if sm_ord > sm_ord_max:
				sm_ord_max = sm_ord
		if sm_ord_min == sm_ord_max:
			diffstart1 += 1
		else:
			break
	sm = chr(int((sm_ord_min + sm_ord_max + 1) / 2))
	i1 = l_first
	i2 = l_last
	try:
		while i1 < i2:
			if l[i1] + diffstart1 == slen or s[l[i1] + diffstart1] < sm:
				i1 += 1
			elif l[i2] + diffstart1 < slen and s[l[i2] + diffstart1] >= sm:
				i2 -= 1
			else:
				ll = l[i1]
				l[i1] = l[i2]
				l[i2] = ll
				i1 += 1
	except:
		print((slen, l_first, l_last, i1, i2, l[i1], l[i2], diffstart, sm))
		return
	rendez(s, slen, l, l_first, i1 - 1, diffstart1)
	rendez(s, slen, l, i1, l_last, diffstart1)

def testcase(s, k):
	slenarray = [0] * (len(s) + 1)
	for i in range(1, len(s) + 1):
		slenarray[i] = slenarray[i - 1] + i
	l = list(range(len(s)))
	rendez(s, len(s), l, 0, len(l) - 1, 0)
	for i in range(len(s)):
		s0 = s[l[i - 1]:] if i > 0 else ''
		s1 = s[l[i]:]
		diffstart = 0
		while diffstart < len(s0) and diffstart < len(s1) and (s0[diffstart] == s1[diffstart]):
			diffstart = diffstart + 1
		slen = slenarray[len(s1)] - slenarray[diffstart]
		if k <= slen:
			d = diffstart + 1
			while k > 0:
				if k <= d:
					print(s1[k - 1])
					k = 0
					break
				else:
					k = k - d
					d = d + 1
		else:
			k = k - slen
		if k == 0:
			break
testcount = int(sys.stdin.readline())
for i in range(testcount):
	s = sys.stdin.readline()[:-1]
	k = int(sys.stdin.readline())
	testcase(s, k)


import sys

def rendez(s, slen, l, l_first, l_last, diffstart):
	if l_first >= l_last:
		return
	diffstart1 = diffstart
	while True:
		sm_ord_min = ord('z') + 1
		sm_ord_max = ord('a') - 2
		for l_i in range(l_first, l_last + 1):
			sm_ord = ord(s[l[l_i] + diffstart1]) if l[l_i] + diffstart1 < slen else ord('a') - 1
			if sm_ord < sm_ord_min:
				sm_ord_min = sm_ord
			if sm_ord > sm_ord_max:
				sm_ord_max = sm_ord
		if sm_ord_min == sm_ord_max:
			diffstart1 += 1
		else:
			break
	sm = chr(int((sm_ord_min + sm_ord_max + 1) / 2))
	i1 = l_first
	i2 = l_last
	try:
		while i1 < i2:
			if l[i1] + diffstart1 == slen or s[l[i1] + diffstart1] < sm:
				i1 += 1
			elif l[i2] + diffstart1 < slen and s[l[i2] + diffstart1] >= sm:
				i2 -= 1
			else:
				ll = l[i1]
				l[i1] = l[i2]
				l[i2] = ll
				i1 += 1
	except:
		print((slen, l_first, l_last, i1, i2, l[i1], l[i2], diffstart, sm))
		return
	rendez(s, slen, l, l_first, i1 - 1, diffstart1)
	rendez(s, slen, l, i1, l_last, diffstart1)

def testcase(s, k):
	slenarray = [0] * (len(s) + 1)
	for i in range(1, len(s) + 1):
		slenarray[i] = slenarray[i - 1] + i
	l = list(range(len(s)))
	rendez(s, len(s), l, 0, len(l) - 1, 0)
	for i in range(len(s)):
		s0 = s[l[i - 1]:] if i > 0 else ''
		s1 = s[l[i]:]
		diffstart = 0
		while diffstart < len(s0) and diffstart < len(s1) and (s0[diffstart] == s1[diffstart]):
			diffstart = diffstart + 1
		slen = slenarray[len(s1)] - slenarray[diffstart]
		if k <= slen:
			d = diffstart + 1
			while k > 0:
				if k <= d:
					print(s1[k - 1])
					k = 0
					break
				else:
					k = k - d
					d = d + 1
		else:
			k = k - slen
		if k == 0:
			break
testcount = int(sys.stdin.readline())
for i in range(testcount):
	s = sys.stdin.readline()[:-1]
	k = int(sys.stdin.readline())
	testcase(s, k)


def foo(text, k):
	stack = [('', list(range(len(text))))]
	while stack != []:
		(prefix, ii) = stack.pop()
		if k < len(prefix):
			return prefix[k]
		k -= len(prefix)
		cs = sorted([(text[i], i + 1) for i in ii if i < len(text)], reverse=True)
		i = 0
		while i < len(cs):
			c = cs[i][0]
			ii2 = [cs[i][1]]
			j = i + 1
			while j < len(cs) and cs[j][0] == c:
				ii2.append(cs[j][1])
				j += 1
			stack.append((prefix + c, ii2))
			i = j
	return None
T = int(input().strip())
for i in range(T):
	text = input().strip()
	k = int(input().strip())
	print(foo(text, k - 1))


string = 'abcdefghijklmnopqrstuvwxyz'
t = int(input())
for _ in range(t):
	ss = input()
	k = int(input()) - 1
	l = len(ss)
	f = 0
	counter = 0
	for ele in string:
		s = [i for i in range(l) if ss[i] == ele]
		s.sort(key=lambda x: ss[x:])
		prev = -1
		for i in s:
			if f == 0:
				start = 0
				if prev != -1:
					while max(i + start, prev + start) < l and ss[i + start] == ss[prev + start]:
						start += 1
				for length in range(start + 1, l - i + 1):
					if f == 0:
						if counter + length > k:
							print(ss[i + k - counter])
							f = 1
							break
						counter += length
				prev = i


import os
import sys
ALPHABET = 'abcdefghijklmnopqrstuvwxyz'

def do_it(base, k):
	base_len = len(base)
	counter = 0
	for letter in ALPHABET:
		sorted_i = [i for i in range(base_len) if base[i] == letter]
		sorted_i.sort(key=lambda x: base[x:])
		prev = None
		for index in sorted_i:
			start = 0
			if prev != None:
				while max(index + start, prev + start) < base_len and base[index + start] == base[prev + start]:
					start += 1
			for length in range(start + 1, base_len - index + 1):
				if counter + length > k:
					return base[index + k - counter]
				counter += length
			prev = index
n = int(input())
for _ in range(n):
	base = input()
	k = int(input()) - 1
	print(do_it(base, k))


n = int(input())
start_s = []
k = []
for i in range(n):
	start_s.append(input())
	k.append(int(input()))
for t in range(n):
	letters = sorted(set(start_s[t]))
	total_l = 0
	found = False
	x = 0
	while not found:
		s = letters[x]
		pos = []
		for i in range(len(start_s[t])):
			if start_s[t][i] == s:
				pos.append(i)
		long_str = [start_s[t][i:] for i in pos]
		long_str.sort()
		prev_ls = ''
		for ls in long_str:
			i = 0
			while i < len(ls) and i < len(prev_ls) and (ls[i] == prev_ls[i]):
				i += 1
			l = sum([j for j in range(i + 1, len(ls) + 1)])
			if total_l + l >= k[t]:
				j = i + 1
				len_substr = 0
				while len_substr < k[t] - total_l:
					len_substr += j
					j += 1
				sub_str = ls[:j - 1]
				print(sub_str[len(sub_str) - (len_substr - (k[t] - total_l)) - 1])
				found = True
				break
			else:
				total_l += l
			prev_ls = ls
		x += 1


def substring_from_index(string, idx):
	for i in range(idx + 1, len(string) + 1):
		yield string[:i]
	return

def substring_from_list(suffixes, k):
	suffixes.sort()
	substrs = ''
	last_suffix = ''
	for suffix in suffixes:
		if suffix == last_suffix:
			continue
		idx = 0
		if last_suffix != '':
			idx = 1
			while idx < len(suffix) and idx < len(last_suffix) and (last_suffix[idx] == suffix[idx]):
				idx = idx + 1
		for substr in substring_from_index(suffix, idx):
			if len(substr) < k:
				k = k - len(substr)
			else:
				return (substr[k], k)
		last_suffix = suffix
	return (None, k)
ALPHABET = ['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']

def make_suffix_dict(word):
	suffix_indexes = dict()
	for (i, ch) in enumerate(word):
		if ch not in suffix_indexes:
			suffix_indexes[ch] = [i]
		else:
			suffix_indexes[ch].append(i)
	return suffix_indexes

def get_suffixes(word, suffix_indexes):
	suffixes = [word[idx:] for idx in suffix_indexes]
	return suffixes

def find_kth_char(word, k):
	suffix_indexes = make_suffix_dict(word)
	for letter in ALPHABET:
		if letter in suffix_indexes:
			suffixes = get_suffixes(word, suffix_indexes[letter])
			(ch, k) = substring_from_list(suffixes, k)
			if ch:
				return ch
test_cases = int(input())
for i in range(0, test_cases):
	line = input()
	k = int(input()) - 1
	print(find_kth_char(line, k))


import sys

def rendez(s, slen, l, l_first, l_last, diffstart):
	if l_first >= l_last:
		return
	diffstart1 = diffstart
	while True:
		sm_ord_min = ord('z') + 1
		sm_ord_max = ord('a') - 2
		for l_i in range(l_first, l_last + 1):
			sm_ord = ord(s[l[l_i] + diffstart1]) if l[l_i] + diffstart1 < slen else ord('a') - 1
			if sm_ord < sm_ord_min:
				sm_ord_min = sm_ord
			if sm_ord > sm_ord_max:
				sm_ord_max = sm_ord
		if sm_ord_min == sm_ord_max:
			diffstart1 += 1
		else:
			break
	sm = chr(int((sm_ord_min + sm_ord_max + 1) / 2))
	i1 = l_first
	i2 = l_last
	try:
		while i1 < i2:
			if l[i1] + diffstart1 == slen or s[l[i1] + diffstart1] < sm:
				i1 += 1
			elif l[i2] + diffstart1 < slen and s[l[i2] + diffstart1] >= sm:
				i2 -= 1
			else:
				ll = l[i1]
				l[i1] = l[i2]
				l[i2] = ll
				i1 += 1
	except:
		print((slen, l_first, l_last, i1, i2, l[i1], l[i2], diffstart, sm))
		return
	rendez(s, slen, l, l_first, i1 - 1, diffstart1)
	rendez(s, slen, l, i1, l_last, diffstart1)

def testcase(s, k):
	slenarray = [0] * (len(s) + 1)
	for i in range(1, len(s) + 1):
		slenarray[i] = slenarray[i - 1] + i
	l = list(range(len(s)))
	rendez(s, len(s), l, 0, len(l) - 1, 0)
	for i in range(len(s)):
		s0 = s[l[i - 1]:] if i > 0 else ''
		s1 = s[l[i]:]
		diffstart = 0
		while diffstart < len(s0) and diffstart < len(s1) and (s0[diffstart] == s1[diffstart]):
			diffstart = diffstart + 1
		slen = slenarray[len(s1)] - slenarray[diffstart]
		if k <= slen:
			d = diffstart + 1
			while k > 0:
				if k <= d:
					print(s1[k - 1])
					k = 0
					break
				else:
					k = k - d
					d = d + 1
		else:
			k = k - slen
		if k == 0:
			break
testcount = int(sys.stdin.readline())
for i in range(testcount):
	s = sys.stdin.readline()[:-1]
	k = int(sys.stdin.readline())
	testcase(s, k)


import sys

def rendez(s, slen, l, l_first, l_last, diffstart):
	if l_first >= l_last:
		return
	diffstart1 = diffstart
	while True:
		sm_ord_min = ord('z') + 1
		sm_ord_max = ord('a') - 2
		for l_i in range(l_first, l_last + 1):
			sm_ord = ord(s[l[l_i] + diffstart1]) if l[l_i] + diffstart1 < slen else ord('a') - 1
			if sm_ord < sm_ord_min:
				sm_ord_min = sm_ord
			if sm_ord > sm_ord_max:
				sm_ord_max = sm_ord
		if sm_ord_min == sm_ord_max:
			diffstart1 += 1
		else:
			break
	sm = chr(int((sm_ord_min + sm_ord_max + 1) / 2))
	i1 = l_first
	i2 = l_last
	try:
		while i1 < i2:
			if l[i1] + diffstart1 == slen or s[l[i1] + diffstart1] < sm:
				i1 += 1
			elif l[i2] + diffstart1 < slen and s[l[i2] + diffstart1] >= sm:
				i2 -= 1
			else:
				ll = l[i1]
				l[i1] = l[i2]
				l[i2] = ll
				i1 += 1
	except:
		print((slen, l_first, l_last, i1, i2, l[i1], l[i2], diffstart, sm))
		return
	rendez(s, slen, l, l_first, i1 - 1, diffstart1)
	rendez(s, slen, l, i1, l_last, diffstart1)

def testcase(s, k):
	slenarray = [0] * (len(s) + 1)
	for i in range(1, len(s) + 1):
		slenarray[i] = slenarray[i - 1] + i
	l = list(range(len(s)))
	rendez(s, len(s), l, 0, len(l) - 1, 0)
	for i in range(len(s)):
		s0 = s[l[i - 1]:] if i > 0 else ''
		s1 = s[l[i]:]
		diffstart = 0
		while diffstart < len(s0) and diffstart < len(s1) and (s0[diffstart] == s1[diffstart]):
			diffstart = diffstart + 1
		slen = slenarray[len(s1)] - slenarray[diffstart]
		if k <= slen:
			d = diffstart + 1
			while k > 0:
				if k <= d:
					print(s1[k - 1])
					k = 0
					break
				else:
					k = k - d
					d = d + 1
		else:
			k = k - slen
		if k == 0:
			break
testcount = int(sys.stdin.readline())
for i in range(testcount):
	s = sys.stdin.readline()[:-1]
	k = int(sys.stdin.readline())
	testcase(s, k)


import time

def lcparray(array, sa, rank):
	lcp = []
	for i in range(len(array)):
		lcp.append(0)
	k = 0
	for i in range(len(array)):
		if rank[i] == len(array) - 1:
			k = 0
			continue
		j = sa[int(rank[i]) + 1]
		while i + k < len(array) and j + k < len(array) and (array[i + k] == array[j + k]):
			k = k + 1
		lcp[int(rank[i])] = k
		if k > 0:
			k = k - 1
	return lcp

def merge(left, right, array):
	if left < right:
		mid = (left + right) // 2
		left = merge(left, mid, array)
		right = merge(mid + 1, right, array)
		return mergesort(left, right)
	else:
		return [array[left]]

def mergesort(left, right):
	p = []
	while len(left) > 0 and len(right) > 0:
		if left[0] < right[0]:
			p.append(left[0])
			left.remove(left[0])
		elif right[0] < left[0]:
			p.append(right[0])
			right.remove(right[0])
		else:
			right.remove(right[0])
	if len(left) != 0:
		p = p + left
	elif len(right) != 0:
		p = p + right
	return p
t = int(input())
s = time.time()
for i in range(t):
	s2 = time.time()
	array = list(input())
	k = int(input())
	rank = merge(0, len(array) - 1, array)
	rank_list = []
	dict3 = {}
	i = -1
	for r in rank:
		i = i + 1
		dict3.update({r: i})
	for x in array:
		rank_list.append(dict3[x])
	j = 1
	while len(rank) != len(array):
		array2 = []
		for i in range(len(rank_list)):
			if i + j < len(rank_list):
				array2.append((rank_list[i], rank_list[i + j]))
			else:
				array2.append((rank_list[i], -1))
		rank = merge(0, len(array2) - 1, array2)
		rank_list = []
		dict1 = {}
		i = -1
		for x in rank:
			i = i + 1
			dict1.update({x: i})
		for x in array2:
			rank_list.append(dict1[x])
		j = j * 2
	sa = []
	dict2 = {}
	i = -1
	for x in rank_list:
		i = i + 1
		dict2.update({x: i})
	for r in range(len(rank_list)):
		sa.append(dict2[r])
	sa_e = time.time()
	total = ''
	t = 0
	lcp_s = time.time()
	lcp = lcparray(array, sa, rank_list)
	lcp_e = time.time()
	for x in sa:
		f = 0
		ar = ''.join(array[x:len(array)])
		index = sa.index(x) - 1
		for j in range(1 + lcp[index], len(ar) + 1):
			if len(total) + t > k:
				f = 1
				break
			if len(total) < 100000:
				total = total + ar[0:j]
			else:
				t = t + len(total)
				total = ''
				total = total + ar[0:j]
		if f == 1:
			break
	print(total[k - t - 1])
et = time.time()


import time

def lcparray(array, sa, rank):
	lcp = []
	for i in range(len(array)):
		lcp.append(0)
	k = 0
	for i in range(len(array)):
		if rank[i] == len(array) - 1:
			k = 0
			continue
		j = sa[int(rank[i]) + 1]
		while i + k < len(array) and j + k < len(array) and (array[i + k] == array[j + k]):
			k = k + 1
		lcp[int(rank[i])] = k
		if k > 0:
			k = k - 1
	return lcp

def merge(left, right, array):
	if left < right:
		mid = (left + right) // 2
		left = merge(left, mid, array)
		right = merge(mid + 1, right, array)
		return mergesort(left, right)
	else:
		return [array[left]]

def mergesort(left, right):
	p = []
	while len(left) > 0 and len(right) > 0:
		if left[0] < right[0]:
			p.append(left[0])
			left.remove(left[0])
		elif right[0] < left[0]:
			p.append(right[0])
			right.remove(right[0])
		else:
			right.remove(right[0])
	if len(left) != 0:
		p = p + left
	elif len(right) != 0:
		p = p + right
	return p
t = int(input())
s = time.time()
for i in range(t):
	s2 = time.time()
	array = list(input())
	k = int(input())
	rank = merge(0, len(array) - 1, array)
	rank_list = []
	dict3 = {}
	i = -1
	for r in rank:
		i = i + 1
		dict3.update({r: i})
	for x in array:
		rank_list.append(dict3[x])
	j = 1
	while len(rank) != len(array):
		array2 = []
		for i in range(len(rank_list)):
			if i + j < len(rank_list):
				array2.append((rank_list[i], rank_list[i + j]))
			else:
				array2.append((rank_list[i], -1))
		rank = merge(0, len(array2) - 1, array2)
		rank_list = []
		dict1 = {}
		i = -1
		for x in rank:
			i = i + 1
			dict1.update({x: i})
		for x in array2:
			rank_list.append(dict1[x])
		j = j * 2
	sa = []
	dict2 = {}
	i = -1
	for x in rank_list:
		i = i + 1
		dict2.update({x: i})
	for r in range(len(rank_list)):
		sa.append(dict2[r])
	sa_e = time.time()
	total = ''
	t = 0
	lcp_s = time.time()
	lcp = lcparray(array, sa, rank_list)
	lcp_e = time.time()
	for x in sa:
		f = 0
		ar = ''.join(array[x:len(array)])
		index = sa.index(x) - 1
		for j in range(1 + lcp[index], len(ar) + 1):
			if len(total) + t > k:
				f = 1
				break
			if len(total) < 100000:
				total = total + ar[0:j]
			else:
				t = t + len(total)
				total = ''
				total = total + ar[0:j]
		if f == 1:
			break
	print(total[k - t - 1])
et = time.time()


def substring_from_index(string, idx):
	for i in range(idx + 1, len(string) + 1):
		yield string[:i]
	return

def substring_from_list(suffixes, k):
	suffixes.sort()
	substrs = ''
	last_suffix = ''
	for suffix in suffixes:
		if suffix == last_suffix:
			continue
		idx = 0
		if last_suffix != '':
			idx = 1
			while idx < len(suffix) and idx < len(last_suffix) and (last_suffix[idx] == suffix[idx]):
				idx = idx + 1
		for substr in substring_from_index(suffix, idx):
			if len(substr) < k:
				k = k - len(substr)
			else:
				return (substr[k], k)
		last_suffix = suffix
	return (None, k)
ALPHABET = ['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']

def make_suffix_dict(word):
	suffix_indexes = dict()
	for (i, ch) in enumerate(word):
		if ch not in suffix_indexes:
			suffix_indexes[ch] = [i]
		else:
			suffix_indexes[ch].append(i)
	return suffix_indexes

def get_suffixes(word, suffix_indexes):
	suffixes = [word[idx:] for idx in suffix_indexes]
	return suffixes

def find_kth_char(word, k):
	suffix_indexes = make_suffix_dict(word)
	for letter in ALPHABET:
		if letter in suffix_indexes:
			suffixes = get_suffixes(word, suffix_indexes[letter])
			(ch, k) = substring_from_list(suffixes, k)
			if ch:
				return ch
test_cases = int(input())
for i in range(0, test_cases):
	line = input()
	k = int(input()) - 1
	print(find_kth_char(line, k))


import sys

def rendez(s, slen, l, l_first, l_last, diffstart):
	if l_first >= l_last:
		return
	diffstart1 = diffstart
	while True:
		sm_ord_min = ord('z') + 1
		sm_ord_max = ord('a') - 2
		for l_i in range(l_first, l_last + 1):
			sm_ord = ord(s[l[l_i] + diffstart1]) if l[l_i] + diffstart1 < slen else ord('a') - 1
			if sm_ord < sm_ord_min:
				sm_ord_min = sm_ord
			if sm_ord > sm_ord_max:
				sm_ord_max = sm_ord
		if sm_ord_min == sm_ord_max:
			diffstart1 += 1
		else:
			break
	sm = chr(int((sm_ord_min + sm_ord_max + 1) / 2))
	i1 = l_first
	i2 = l_last
	try:
		while i1 < i2:
			if l[i1] + diffstart1 == slen or s[l[i1] + diffstart1] < sm:
				i1 += 1
			elif l[i2] + diffstart1 < slen and s[l[i2] + diffstart1] >= sm:
				i2 -= 1
			else:
				ll = l[i1]
				l[i1] = l[i2]
				l[i2] = ll
				i1 += 1
	except:
		print((slen, l_first, l_last, i1, i2, l[i1], l[i2], diffstart, sm))
		return
	rendez(s, slen, l, l_first, i1 - 1, diffstart1)
	rendez(s, slen, l, i1, l_last, diffstart1)

def testcase(s, k):
	slenarray = [0] * (len(s) + 1)
	for i in range(1, len(s) + 1):
		slenarray[i] = slenarray[i - 1] + i
	l = list(range(len(s)))
	rendez(s, len(s), l, 0, len(l) - 1, 0)
	for i in range(len(s)):
		s0 = s[l[i - 1]:] if i > 0 else ''
		s1 = s[l[i]:]
		diffstart = 0
		while diffstart < len(s0) and diffstart < len(s1) and (s0[diffstart] == s1[diffstart]):
			diffstart = diffstart + 1
		slen = slenarray[len(s1)] - slenarray[diffstart]
		if k <= slen:
			d = diffstart + 1
			while k > 0:
				if k <= d:
					print(s1[k - 1])
					k = 0
					break
				else:
					k = k - d
					d = d + 1
		else:
			k = k - slen
		if k == 0:
			break
testcount = int(sys.stdin.readline())
for i in range(testcount):
	s = sys.stdin.readline()[:-1]
	k = int(sys.stdin.readline())
	testcase(s, k)


import sys

def rendez(s, slen, l, l_first, l_last, diffstart):
	if l_first >= l_last:
		return
	diffstart1 = diffstart
	while True:
		sm_ord_min = ord('z') + 1
		sm_ord_max = ord('a') - 2
		for l_i in range(l_first, l_last + 1):
			sm_ord = ord(s[l[l_i] + diffstart1]) if l[l_i] + diffstart1 < slen else ord('a') - 1
			if sm_ord < sm_ord_min:
				sm_ord_min = sm_ord
			if sm_ord > sm_ord_max:
				sm_ord_max = sm_ord
		if sm_ord_min == sm_ord_max:
			diffstart1 += 1
		else:
			break
	sm = chr(int((sm_ord_min + sm_ord_max + 1) / 2))
	i1 = l_first
	i2 = l_last
	try:
		while i1 < i2:
			if l[i1] + diffstart1 == slen or s[l[i1] + diffstart1] < sm:
				i1 += 1
			elif l[i2] + diffstart1 < slen and s[l[i2] + diffstart1] >= sm:
				i2 -= 1
			else:
				ll = l[i1]
				l[i1] = l[i2]
				l[i2] = ll
				i1 += 1
	except:
		print((slen, l_first, l_last, i1, i2, l[i1], l[i2], diffstart, sm))
		return
	rendez(s, slen, l, l_first, i1 - 1, diffstart1)
	rendez(s, slen, l, i1, l_last, diffstart1)

def testcase(s, k):
	slenarray = [0] * (len(s) + 1)
	for i in range(1, len(s) + 1):
		slenarray[i] = slenarray[i - 1] + i
	l = list(range(len(s)))
	rendez(s, len(s), l, 0, len(l) - 1, 0)
	for i in range(len(s)):
		s0 = s[l[i - 1]:] if i > 0 else ''
		s1 = s[l[i]:]
		diffstart = 0
		while diffstart < len(s0) and diffstart < len(s1) and (s0[diffstart] == s1[diffstart]):
			diffstart = diffstart + 1
		slen = slenarray[len(s1)] - slenarray[diffstart]
		if k <= slen:
			d = diffstart + 1
			while k > 0:
				if k <= d:
					print(s1[k - 1])
					k = 0
					break
				else:
					k = k - d
					d = d + 1
		else:
			k = k - slen
		if k == 0:
			break
testcount = int(sys.stdin.readline())
for i in range(testcount):
	s = sys.stdin.readline()[:-1]
	k = int(sys.stdin.readline())
	testcase(s, k)


ALPHABET = 'abcdefghijklmnopqrstuvwxyz'

def do_it(base, k):
	base_len = len(base)
	counter = 0
	for letter in ALPHABET:
		sorted_i = [i for i in range(base_len) if base[i] == letter]
		sorted_i.sort(key=lambda x: base[x:])
		prev = None
		for index in sorted_i:
			start = 0
			if prev != None:
				while max(index + start, prev + start) < base_len and base[index + start] == base[prev + start]:
					start += 1
			for length in range(start + 1, base_len - index + 1):
				if counter + length > k:
					return base[index + k - counter]
				counter += length
			prev = index
n = int(input())
for _ in range(n):
	base = input()
	k = int(input()) - 1
	print(do_it(base, k))


import sys

def rendez(s, slen, l, l_first, l_last, diffstart):
	if l_first >= l_last:
		return
	diffstart1 = diffstart
	while True:
		sm_ord_min = ord('z') + 1
		sm_ord_max = ord('a') - 2
		for l_i in range(l_first, l_last + 1):
			sm_ord = ord(s[l[l_i] + diffstart1]) if l[l_i] + diffstart1 < slen else ord('a') - 1
			if sm_ord < sm_ord_min:
				sm_ord_min = sm_ord
			if sm_ord > sm_ord_max:
				sm_ord_max = sm_ord
		if sm_ord_min == sm_ord_max:
			diffstart1 += 1
		else:
			break
	sm = chr(int((sm_ord_min + sm_ord_max + 1) / 2))
	i1 = l_first
	i2 = l_last
	try:
		while i1 < i2:
			if l[i1] + diffstart1 == slen or s[l[i1] + diffstart1] < sm:
				i1 += 1
			elif l[i2] + diffstart1 < slen and s[l[i2] + diffstart1] >= sm:
				i2 -= 1
			else:
				ll = l[i1]
				l[i1] = l[i2]
				l[i2] = ll
				i1 += 1
	except:
		print((slen, l_first, l_last, i1, i2, l[i1], l[i2], diffstart, sm))
		return
	rendez(s, slen, l, l_first, i1 - 1, diffstart1)
	rendez(s, slen, l, i1, l_last, diffstart1)

def testcase(s, k):
	slenarray = [0] * (len(s) + 1)
	for i in range(1, len(s) + 1):
		slenarray[i] = slenarray[i - 1] + i
	l = list(range(len(s)))
	rendez(s, len(s), l, 0, len(l) - 1, 0)
	for i in range(len(s)):
		s0 = s[l[i - 1]:] if i > 0 else ''
		s1 = s[l[i]:]
		diffstart = 0
		while diffstart < len(s0) and diffstart < len(s1) and (s0[diffstart] == s1[diffstart]):
			diffstart = diffstart + 1
		slen = slenarray[len(s1)] - slenarray[diffstart]
		if k <= slen:
			d = diffstart + 1
			while k > 0:
				if k <= d:
					print(s1[k - 1])
					k = 0
					break
				else:
					k = k - d
					d = d + 1
		else:
			k = k - slen
		if k == 0:
			break
testcount = int(sys.stdin.readline())
for i in range(testcount):
	s = sys.stdin.readline()[:-1]
	k = int(sys.stdin.readline())
	testcase(s, k)


import sys

def rendez(s, slen, l, l_first, l_last, diffstart):
	if l_first >= l_last:
		return
	diffstart1 = diffstart
	while True:
		sm_ord_min = ord('z') + 1
		sm_ord_max = ord('a') - 2
		for l_i in range(l_first, l_last + 1):
			sm_ord = ord(s[l[l_i] + diffstart1]) if l[l_i] + diffstart1 < slen else ord('a') - 1
			if sm_ord < sm_ord_min:
				sm_ord_min = sm_ord
			if sm_ord > sm_ord_max:
				sm_ord_max = sm_ord
		if sm_ord_min == sm_ord_max:
			diffstart1 += 1
		else:
			break
	sm = chr(int((sm_ord_min + sm_ord_max + 1) / 2))
	i1 = l_first
	i2 = l_last
	try:
		while i1 < i2:
			if l[i1] + diffstart1 == slen or s[l[i1] + diffstart1] < sm:
				i1 += 1
			elif l[i2] + diffstart1 < slen and s[l[i2] + diffstart1] >= sm:
				i2 -= 1
			else:
				ll = l[i1]
				l[i1] = l[i2]
				l[i2] = ll
				i1 += 1
	except:
		print((slen, l_first, l_last, i1, i2, l[i1], l[i2], diffstart, sm))
		return
	rendez(s, slen, l, l_first, i1 - 1, diffstart1)
	rendez(s, slen, l, i1, l_last, diffstart1)

def testcase(s, k):
	slenarray = [0] * (len(s) + 1)
	for i in range(1, len(s) + 1):
		slenarray[i] = slenarray[i - 1] + i
	l = list(range(len(s)))
	rendez(s, len(s), l, 0, len(l) - 1, 0)
	for i in range(len(s)):
		s0 = s[l[i - 1]:] if i > 0 else ''
		s1 = s[l[i]:]
		diffstart = 0
		while diffstart < len(s0) and diffstart < len(s1) and (s0[diffstart] == s1[diffstart]):
			diffstart = diffstart + 1
		slen = slenarray[len(s1)] - slenarray[diffstart]
		if k <= slen:
			d = diffstart + 1
			while k > 0:
				if k <= d:
					print(s1[k - 1])
					k = 0
					break
				else:
					k = k - d
					d = d + 1
		else:
			k = k - slen
		if k == 0:
			break
testcount = int(sys.stdin.readline())
for i in range(testcount):
	s = sys.stdin.readline()[:-1]
	k = int(sys.stdin.readline())
	testcase(s, k)


def substring_from_index(string, idx):
	for i in range(idx + 1, len(string) + 1):
		yield string[:i]
	return

def substring_from_list(suffixes, k):
	suffixes.sort()
	substrs = ''
	last_suffix = ''
	for suffix in suffixes:
		if suffix == last_suffix:
			continue
		idx = 0
		if last_suffix != '':
			idx = 1
			while idx < len(suffix) and idx < len(last_suffix) and (last_suffix[idx] == suffix[idx]):
				idx = idx + 1
		for substr in substring_from_index(suffix, idx):
			if len(substr) < k:
				k = k - len(substr)
			else:
				return (substr[k], k)
		last_suffix = suffix
	return (None, k)
ALPHABET = ['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']

def make_suffix_dict(word):
	suffix_indexes = dict()
	for (i, ch) in enumerate(word):
		if ch not in suffix_indexes:
			suffix_indexes[ch] = [i]
		else:
			suffix_indexes[ch].append(i)
	return suffix_indexes

def get_suffixes(word, suffix_indexes):
	suffixes = [word[idx:] for idx in suffix_indexes]
	return suffixes

def find_kth_char(word, k):
	suffix_indexes = make_suffix_dict(word)
	for letter in ALPHABET:
		if letter in suffix_indexes:
			suffixes = get_suffixes(word, suffix_indexes[letter])
			(ch, k) = substring_from_list(suffixes, k)
			if ch:
				return ch
test_cases = int(input())
for i in range(0, test_cases):
	line = input()
	k = int(input()) - 1
	print(find_kth_char(line, k))


ALPHABET = 'abcdefghijklmnopqrstuvwxyz'

def do_it(base, k):
	base_len = len(base)
	counter = 0
	for letter in ALPHABET:
		sorted_i = [i for i in range(base_len) if base[i] == letter]
		sorted_i.sort(key=lambda x: base[x:])
		prev = None
		for index in sorted_i:
			start = 0
			if prev != None:
				while max(index + start, prev + start) < base_len and base[index + start] == base[prev + start]:
					start += 1
			for length in range(start + 1, base_len - index + 1):
				if counter + length > k:
					return base[index + k - counter]
				counter += length
			prev = index
n = int(input())
for _ in range(n):
	base = input()
	k = int(input()) - 1
	print(do_it(base, k))


import sys

def rendez(s, slen, l, l_first, l_last, diffstart):
	if l_first >= l_last:
		return
	diffstart1 = diffstart
	while True:
		sm_ord_min = ord('z') + 1
		sm_ord_max = ord('a') - 2
		for l_i in range(l_first, l_last + 1):
			sm_ord = ord(s[l[l_i] + diffstart1]) if l[l_i] + diffstart1 < slen else ord('a') - 1
			if sm_ord < sm_ord_min:
				sm_ord_min = sm_ord
			if sm_ord > sm_ord_max:
				sm_ord_max = sm_ord
		if sm_ord_min == sm_ord_max:
			diffstart1 += 1
		else:
			break
	sm = chr(int((sm_ord_min + sm_ord_max + 1) / 2))
	i1 = l_first
	i2 = l_last
	try:
		while i1 < i2:
			if l[i1] + diffstart1 == slen or s[l[i1] + diffstart1] < sm:
				i1 += 1
			elif l[i2] + diffstart1 < slen and s[l[i2] + diffstart1] >= sm:
				i2 -= 1
			else:
				ll = l[i1]
				l[i1] = l[i2]
				l[i2] = ll
				i1 += 1
	except:
		print((slen, l_first, l_last, i1, i2, l[i1], l[i2], diffstart, sm))
		return
	rendez(s, slen, l, l_first, i1 - 1, diffstart1)
	rendez(s, slen, l, i1, l_last, diffstart1)

def testcase(s, k):
	slenarray = [0] * (len(s) + 1)
	for i in range(1, len(s) + 1):
		slenarray[i] = slenarray[i - 1] + i
	l = list(range(len(s)))
	rendez(s, len(s), l, 0, len(l) - 1, 0)
	for i in range(len(s)):
		s0 = s[l[i - 1]:] if i > 0 else ''
		s1 = s[l[i]:]
		diffstart = 0
		while diffstart < len(s0) and diffstart < len(s1) and (s0[diffstart] == s1[diffstart]):
			diffstart = diffstart + 1
		slen = slenarray[len(s1)] - slenarray[diffstart]
		if k <= slen:
			d = diffstart + 1
			while k > 0:
				if k <= d:
					print(s1[k - 1])
					k = 0
					break
				else:
					k = k - d
					d = d + 1
		else:
			k = k - slen
		if k == 0:
			break
testcount = int(sys.stdin.readline())
for i in range(testcount):
	s = sys.stdin.readline()[:-1]
	k = int(sys.stdin.readline())
	testcase(s, k)


from collections import defaultdict

def func1(s, n):
	d = defaultdict(list)
	sl = len(s)
	for i in range(sl):
		d[s[i]].append(i)
	for i in sorted(d.keys()):
		d[i].sort(key=lambda x: s[x:])
		pre = None
		cm_len = 0
		for j in d[i]:
			nex = s[j:]
			ind = 0
			if pre:
				try:
					while nex[:ind] == pre[:ind]:
						ind += 1
				except:
					pass
			for l in range(ind, len(nex) + 1):
				z = l
				if n - z > 0:
					n -= z
				else:
					return nex[n - 1]
			pre = nex
for i in range(int(input())):
	x = func1(input().strip(), int(input()))
	print(x)


def foo(text, k):
	stack = [('', list(range(len(text))))]
	while stack != []:
		(prefix, ii) = stack.pop()
		if k < len(prefix):
			return prefix[k]
		k -= len(prefix)
		cs = sorted([(text[i], i + 1) for i in ii if i < len(text)], reverse=True)
		i = 0
		while i < len(cs):
			c = cs[i][0]
			ii2 = [cs[i][1]]
			j = i + 1
			while j < len(cs) and cs[j][0] == c:
				ii2.append(cs[j][1])
				j += 1
			stack.append((prefix + c, ii2))
			i = j
	return None
T = int(input().strip())
for i in range(T):
	text = input().strip()
	k = int(input().strip())
	print(foo(text, k - 1))


def foo(text, k):
	stack = [('', list(range(len(text))))]
	while stack != []:
		(prefix, ii) = stack.pop()
		if k < len(prefix):
			return prefix[k]
		k -= len(prefix)
		cs = sorted([(text[i], i + 1) for i in ii if i < len(text)], reverse=True)
		i = 0
		while i < len(cs):
			c = cs[i][0]
			ii2 = [cs[i][1]]
			j = i + 1
			while j < len(cs) and cs[j][0] == c:
				ii2.append(cs[j][1])
				j += 1
			stack.append((prefix + c, ii2))
			i = j
	return None
T = int(input().strip())
for i in range(T):
	text = input().strip()
	k = int(input().strip())
	print(foo(text, k - 1))


def foo(text, k):
	stack = [('', list(range(len(text))))]
	while stack != []:
		(prefix, ii) = stack.pop()
		if k < len(prefix):
			return prefix[k]
		k -= len(prefix)
		cs = sorted([(text[i], i + 1) for i in ii if i < len(text)], reverse=True)
		i = 0
		while i < len(cs):
			c = cs[i][0]
			ii2 = [cs[i][1]]
			j = i + 1
			while j < len(cs) and cs[j][0] == c:
				ii2.append(cs[j][1])
				j += 1
			stack.append((prefix + c, ii2))
			i = j
	return None
T = int(input().strip())
for i in range(T):
	text = input().strip()
	k = int(input().strip())
	print(foo(text, k - 1))


n = int(input())
start_s = []
k = []
for i in range(n):
	start_s.append(input())
	k.append(int(input()))
for t in range(n):
	letters = sorted(set(start_s[t]))
	total_l = 0
	found = False
	x = 0
	while not found:
		s = letters[x]
		pos = []
		for i in range(len(start_s[t])):
			if start_s[t][i] == s:
				pos.append(i)
		long_str = [start_s[t][i:] for i in pos]
		long_str.sort()
		prev_ls = ''
		for ls in long_str:
			i = 0
			while i < len(ls) and i < len(prev_ls) and (ls[i] == prev_ls[i]):
				i += 1
			l = sum([j for j in range(i + 1, len(ls) + 1)])
			if total_l + l >= k[t]:
				j = i + 1
				len_substr = 0
				while len_substr < k[t] - total_l:
					len_substr += j
					j += 1
				sub_str = ls[:j - 1]
				print(sub_str[len(sub_str) - (len_substr - (k[t] - total_l)) - 1])
				found = True
				break
			else:
				total_l += l
			prev_ls = ls
		x += 1


def foo(text, k):
	stack = [('', list(range(len(text))))]
	while stack != []:
		(prefix, ii) = stack.pop()
		if k < len(prefix):
			return prefix[k]
		k -= len(prefix)
		cs = sorted([(text[i], i + 1) for i in ii if i < len(text)], reverse=True)
		i = 0
		while i < len(cs):
			c = cs[i][0]
			ii2 = [cs[i][1]]
			j = i + 1
			while j < len(cs) and cs[j][0] == c:
				ii2.append(cs[j][1])
				j += 1
			stack.append((prefix + c, ii2))
			i = j
	return None
T = int(input().strip())
for i in range(T):
	text = input().strip()
	k = int(input().strip())
	print(foo(text, k - 1))


def foo(text, k):
	stack = [('', list(range(len(text))))]
	while stack != []:
		(prefix, ii) = stack.pop()
		if k < len(prefix):
			return prefix[k]
		k -= len(prefix)
		cs = sorted([(text[i], i + 1) for i in ii if i < len(text)], reverse=True)
		i = 0
		while i < len(cs):
			c = cs[i][0]
			ii2 = [cs[i][1]]
			j = i + 1
			while j < len(cs) and cs[j][0] == c:
				ii2.append(cs[j][1])
				j += 1
			stack.append((prefix + c, ii2))
			i = j
	return None
T = int(input().strip())
for i in range(T):
	text = input().strip()
	k = int(input().strip())
	print(foo(text, k - 1))


def foo(text, k):
	stack = [('', list(range(len(text))))]
	while stack != []:
		(prefix, ii) = stack.pop()
		if k < len(prefix):
			return prefix[k]
		k -= len(prefix)
		cs = sorted([(text[i], i + 1) for i in ii if i < len(text)], reverse=True)
		i = 0
		while i < len(cs):
			c = cs[i][0]
			ii2 = [cs[i][1]]
			j = i + 1
			while j < len(cs) and cs[j][0] == c:
				ii2.append(cs[j][1])
				j += 1
			stack.append((prefix + c, ii2))
			i = j
	return None
T = int(input().strip())
for i in range(T):
	text = input().strip()
	k = int(input().strip())
	print(foo(text, k - 1))


import math
import os
import random
import re
import sys

def foo(text, k):
	stack = [('', list(range(len(text))))]
	while stack != []:
		(prefix, ii) = stack.pop()
		if k < len(prefix):
			return prefix[k]
		k -= len(prefix)
		cs = sorted([(text[i], i + 1) for i in ii if i < len(text)], reverse=True)
		i = 0
		while i < len(cs):
			c = cs[i][0]
			ii2 = [cs[i][1]]
			j = i + 1
			while j < len(cs) and cs[j][0] == c:
				ii2.append(cs[j][1])
				j += 1
			stack.append((prefix + c, ii2))
			i = j
	return None
T = int(input().strip())
for i in range(T):
	text = input().strip()
	k = int(input().strip())
	print(foo(text, k - 1))