Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

Sheokand loves strings. Chef has $N$ strings $S_{1}, S_{2}, \dots, S_{N}$ which he wants to give to Sheokand; however, he doesn't want to give them away for free, so Sheokand must first correctly answer $Q$ queries Chef asks him.

In each query, Chef tells Sheokand an integer $R$ and a string $P$. Consider Chef's strings $S_{1}$ through $S_{R}$. Out of these strings, consider all strings such that their longest common prefix with $P$ is maximum possible. Sheokand should find the lexicographically smallest of these strings.

Sheokand is busy with his exams. Can you solve the queries for him?

------  Input ------
The first line of the input contains a single integer $N$.
$N$ lines follow. For each valid $i$, the $i$-th of these lines contains Chef's string $S_{i}$.
The next line contains a single integer $Q$.
The following $Q$ lines describe queries. Each of these lines contains an interger $R$, followed by a space and a string $P$.

------  Output ------
For each query, print a single line containing the string that satisfies the required conditions — the answer to that query.

------  Constraints  ------
$1 ≤ N ≤ 100,000$ 
$1 ≤ |S_{i}| ≤ 10$ for each valid $i$
$1 ≤ Q ≤ 100,000$
$1 ≤ R ≤ N$
$1 ≤ |P| ≤ 10$

------  Subtasks ------
Subtask #1 (30 points): $1 ≤ N, R ≤ 1,000$

Subtask #2 (70 points): original constraints

----- Sample Input 1 ------ 
4
abcd
abce
abcdex
abcde
3
3 abcy
3 abcde
4 abcde
----- Sample Output 1 ------ 
abcd
abcdex
abcde
----- explanation 1 ------ 
Query 1: For strings $S_{1}$ through $S_{3}$, the longest common prefix is always "abc", but "abcd" is the lexicographically smallest of these three strings.

Query 2: For strings $S_{1}$ through $S_{3}$, the longest common prefix with maximum length is "abcde" and the only string for which it is the LCP is "abcdex", so this is the answer.

Query 3: For strings $S_{1}$ through $S_{4}$, the longest common prefix with maximum length is "abcde"; it is the LCP for strings "abcdex" and "abcde", but "abcde" is the lexicographically smaller string, so it is the answer.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures


Solutions:
from collections import defaultdict
TrieNode = lambda : defaultdict(TrieNode)
trie = TrieNode()
words = []
trie['idx'] = 0

def insert(w, cur, idx):
	for c in w:
		if c not in cur:
			cur = cur[c]
			cur['idx'] = idx
		else:
			cur = cur[c]
	cur['isWord'] = True
	if '$' not in cur:
		cur['$'] = idx

def search(word, cur, idx):
	for i in word:
		if i not in cur or cur[i]['idx'] > idx:
			break
		pre = cur
		cur = cur[i]
	while True:
		a = []
		if cur['isWord'] and cur['$'] <= idx:
			return cur['$']
		else:
			for i in 'abcdefghijklmnopqrstuvwxyz':
				if i in cur and cur[i]['idx'] <= idx:
					a.append(i)
			a.sort()
			cur = cur[a[0]]
n = int(input())
for i in range(n):
	x = input().strip()
	words.append(x)
	insert(x, trie, i)
for i in range(int(input())):
	(idx, x) = list(input().split())
	idx = int(idx)
	idx -= 1
	print(words[search(x, trie, idx)])


import sys

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

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

def print(arg, *argv, end=None):
	sys.stdout.write(str(arg))
	for i in argv:
		sys.stdout.write(' ' + str(i))
	sys.stdout.write(end) if end else sys.stdout.write('\n')

class Node(object):

	def __init__(self, idx):
		self.isWord = False
		self.children = {}
		self.idx = idx
		self.end = None

class Trie(object):

	def __init__(self):
		self.root = Node(0)

	def insert(self, word, idx):
		tmp = self.root
		for i in word:
			if i not in tmp.children:
				tmp.children[i] = Node(idx)
			tmp = tmp.children[i]
		tmp.isWord = True
		if tmp.end == None:
			tmp.end = idx

	def search(self, word, idx):
		tmp = self.root
		for i in word:
			if i not in tmp.children or tmp.children[i].idx > idx:
				break
			tmp = tmp.children[i]
		while True:
			a = []
			if tmp.isWord and tmp.end <= idx:
				return tmp.end
			else:
				for i in tmp.children:
					if tmp.children[i].idx <= idx:
						a.append(i)
				a.sort()
				tmp = tmp.children[a[0]]

def solve():
	t = 1
	while t:
		t -= 1
		n = int(input())
		s = []
		trie = Trie()
		for i in range(n):
			x = input().strip()
			s.append(x)
			trie.insert(x, i)
		for q in range(int(input())):
			(idx, x) = input().split()
			idx = int(idx)
			idx -= 1
			print(s[trie.search(x, idx)])
solve()


class node:

	def __init__(self, index, eow=False):
		self.index = index
		self.characters = {}
		self.eow = eow
		self.end = None

def insert(root, word, ind):
	for i in word:
		if i in root.characters:
			root = root.characters[i]
		else:
			new = node(ind)
			root.characters[i] = new
			root = new
	root.eow = True
	if root.end == None:
		root.end = ind

def search(root, word, ind):
	a = []
	for i in word:
		if i in root.characters and root.characters[i].index <= ind:
			root = root.characters[i]
		else:
			break
	while True:
		a = []
		if root.eow and root.end <= ind:
			return root.end
		else:
			for i in root.characters:
				if root.characters[i].index <= ind:
					a.append(i)
			a.sort()
			root = root.characters[a[0]]
root_node = node(1)
a = []
for i in range(1, int(input()) + 1):
	s = input()
	insert(root_node, s, i)
	a.append(s)
for _ in range(int(input())):
	(idx, s) = input().split()
	print(a[search(root_node, s, int(idx)) - 1])


search = {}
n = int(input())
read = []
for i in range(n):
	read.append(input())
for i in range(n):
	search[i] = []
q = int(input())
for i in range(q):
	(na, s) = input().split()
	na = int(na)
	na = na - 1
	search[na].append([i, s])
result = [0] * q
lookup = {}
mini = read[0]
for i in range(n):
	temp = ''
	for j in range(len(read[i])):
		temp += read[i][j]
		if temp in lookup:
			lookup[temp] = min(lookup[temp], read[i])
		else:
			lookup[temp] = read[i]
	mini = min(mini, read[i])
	for s1 in search[i]:
		string = s1[1]
		index = s1[0]
		temp = ''
		ans = ''
		for j in range(len(string)):
			temp += string[j]
			if temp in lookup:
				ans = lookup[temp]
		if not ans:
			ans = mini
		result[index] = ans
for i in result:
	print(i)


class Node:

	def __init__(self):
		self.key = {}
		self.leaf = False

class Trie:

	def __init__(self):
		self.root = Node()

	def insert(self, word):
		x = self.root
		for letter in word:
			if x.key.get(letter):
				x = x.key[letter]
			else:
				x.key[letter] = Node()
				x = x.key[letter]
		x.leaf = True

	def search(self, word):
		ans = ''
		x = self.root
		for letter in word:
			if x.key.get(letter):
				ans = ans + letter
				x = x.key[letter]
			else:
				break
		if not x.leaf:
			while not x.leaf:
				for i in sorted(x.key.keys()):
					if x.key.get(i):
						ans = ans + i
						x = x.key[i]
						break
			return ans
		return ans
strings = []
t = Trie()
for _ in range(int(input())):
	strings.append(input())
commands = []
answer = []
for _ in range(int(input())):
	commands.append(input().split())
	commands[_].append(_)
	answer.append(0)
	commands[_][0] = int(commands[_][0])
commands = sorted(commands)
m = 0
for command in commands:
	if int(command[0]) > m:
		for string in range(m, int(command[0])):
			t.insert(strings[string])
		m = int(command[0])
	answer[command[2]] = t.search(command[1])
for i in answer:
	print(i)


n = int(input())
d = {}
a = []
output = []
output.append(0)
for i in range(n):
	an = input()
	a.append(an)
check = a[0]
checkint = 0
for i in range(1, n):
	if check > a[i]:
		check = a[i]
		output.append(i)
	else:
		output.append(output[-1])
for i in range(n):
	k = len(a[i])
	for j in range(k):
		s = a[i][:j + 1]
		if s not in d:
			d[s] = [i]
		elif a[d[s][-1]] > a[i]:
			d[s].append(i)
k = int(input())
for i in range(k):
	(x, y) = input().split()
	x = int(x)
	l = len(y)
	while l > 0:
		ma = 'zzzzzzzzzzzzzz'
		if y[0:l] in d:
			for j in sorted(d[y[0:l]]):
				if j >= x:
					break
				if a[j] < ma:
					ma = a[j]
			if ma != 'zzzzzzzzzzzzzz':
				break
		l -= 1
	if ma != 'zzzzzzzzzzzzzz':
		print(ma)
		continue
	print(a[output[x - 1]])


from collections import defaultdict
st = defaultdict(list)
ln = defaultdict(int)
t = int(input())
for ijk in range(0, t):
	s = input().strip()
	n = len(s)
	for i in range(n, -1, -1):
		if ln[s[:i]] == 0:
			st[s[:i]].append([ijk + 1, s])
			ln[s[:i]] += 1
		elif s < st[s[:i]][-1][1]:
			st[s[:i]].append([ijk + 1, s])
			ln[s[:i]] += 1
q = int(input())
for ijk in range(0, q):
	(r, p) = input().strip().split()
	r = int(r)
	n = len(p)
	y = ''
	for x in range(n, -1, -1):
		a = p[:x]
		l = st[a]
		if a in st:
			for i in range(0, len(l)):
				c = l[i][0]
				if c <= r:
					y = l[i][1]
					continue
		if y != '':
			break
	if y == '':
		print(st[''][0][1])
	else:
		print(y)


class TrieNode:

	def __init__(self, char: str, R: int):
		self.char = char
		self.children = [None] * 26
		self.min_children = []
		self.word_finished_at = 0
		self.min_child = None
		self.min_R = R

	def add(self, word: str, R: int):
		node = self
		for char in word:
			index = ord(char) - ord('a')
			if node.children[index] is None:
				new_node = TrieNode(char, R)
				node.children[index] = new_node
				if node.min_child is None:
					node.min_child = new_node
					node.min_children.append(new_node)
				elif char < node.min_child.char:
					node.min_child = new_node
					node.min_children.append(new_node)
			node = node.children[index]
		if node.word_finished_at == 0:
			node.word_finished_at = R

	def find_match(self, word: str, R: int):
		node = self
		match = ''
		for char in word:
			index = ord(char) - ord('a')
			if node.children[index] is not None:
				if node.children[index].min_R <= R:
					node = node.children[index]
					match += node.char
				else:
					break
			else:
				break
		if node.word_finished_at > 0 and node.word_finished_at <= R:
			return match
		while node.word_finished_at == 0 or node.word_finished_at > R:
			if node.min_child.min_R <= R:
				node = node.min_child
			else:
				for child in reversed(node.min_children):
					if child.min_R <= R:
						node = child
						break
			match += node.char
		return match
root = TrieNode('*', 99999999)
N = int(input())
S = set()
for i in range(N):
	string = input()
	if string not in S:
		root.add(string, i + 1)
		S.add(string)
m = int(input())
for _ in range(m):
	line = input().split()
	R = int(line[0])
	query = line[1]
	print(root.find_match(query, R))


n = input()
n = int(n)
s = []
d1 = dict()
l5 = [None] * n
l6 = [None] * n
ans1 = ''
for j in range(n):
	ele = input()
	if len(ans1) == 0:
		ans1 = ele
	elif ele < ans1:
		ans1 = ele
	l5[j] = ans1
	s.append(ele)
	for i in range(len(ele)):
		if ele[0:i + 1] not in d1:
			l1 = []
			l1.append((j, s[j]))
			d1[ele[0:i + 1]] = l1
		else:
			l1 = d1[ele[0:i + 1]]
			pg = l1[len(l1) - 1][1]
			if pg < s[j]:
				l1.append((j, pg))
			else:
				l1.append((j, s[j]))
			d1[ele[0:i + 1]] = l1
q = input()
q = int(q)
while q > 0:
	pg = input()
	pg = pg.split(' ')
	r = int(pg[0])
	p = pg[1]
	ans = ''
	p1 = ''
	if len(p) == 0:
		print(l5[r - 1])
	elif p[0] not in d1:
		print(l5[r - 1])
	else:
		for i in range(len(p), 0, -1):
			temp = p[0:i]
			if temp in d1:
				l1 = d1[temp]
				low = 0
				high = len(l1) - 1
				flag = 0
				while low < high:
					mid = (low + high) / 2
					mid = int(mid)
					if l1[mid][0] + 1 == r:
						flag = 1
						ans = l1[mid][1]
						break
					elif l1[mid][0] + 1 > r:
						high = mid - 1
					else:
						low = mid + 1
				if flag == 1:
					break
				elif l1[low][0] + 1 > r:
					if low != 0:
						ans = l1[low - 1][1]
				else:
					ans = l1[low][1]
			if len(ans) > 0:
				break
		if len(ans) == 0:
			print(l5[r - 1])
		else:
			print(ans)
	q -= 1


ROOT = dict()
(words, queries, results) = ([], [], [])

def add_word(word, root=ROOT):
	for letter in word + '$':
		if letter not in root:
			root[letter] = dict()
		root = root[letter]

def solve(word, root=ROOT):
	ans = ''
	for letter in word:
		if letter not in root:
			break
		root = root[letter]
		ans += letter
	while root:
		child = min(root)
		ans += child
		root = root[child]
	return ans[:-1]
for _ in range(int(input())):
	words.append(input().strip())
for qid in range(int(input())):
	(num, word) = input().split()
	queries.append((int(num), word, qid))
last_word_added = -1
for (num, word, qid) in sorted(queries, key=lambda x: x[0]):
	while num > last_word_added + 1:
		add_word(words[last_word_added + 1])
		last_word_added += 1
	ans = solve(word)
	results.append((qid, ans))
for (qid, ans) in sorted(results, key=lambda x: x[0]):
	print(ans)


ROOT = dict()
alpha = ['$', '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']
word_list = []
queries = []

def add_word(word):
	word = word + '$'
	root = ROOT
	for letter in word:
		if letter not in root:
			root[letter] = dict()
		root = root[letter]
for _ in range(int(input())):
	word_list.append(input().strip())
last_word_added = -1
for qid in range(int(input())):
	(num, word) = input().split()
	num = int(num)
	queries.append((num, word, qid))
queries.sort(key=lambda x: x[0])
results = []
for (num, word, qid) in queries:
	while num > last_word_added + 1:
		add_word(word_list[last_word_added + 1])
		last_word_added += 1
	ans = ''
	root = ROOT
	lim = len(word)
	pos = 0
	for letter in word:
		if letter not in root:
			break
		root = root[letter]
		ans += letter
	while root:
		key = min(root)
		ans += key
		root = root[key]
	results.append((qid, ans[:-1]))
results.sort(key=lambda x: x[0])
for (qid, ans) in results:
	print(ans)


def insert(oldic, string, depth=0):
	if type(oldic) == dict:
		dic = oldic.copy()
		if string[depth] in dic.keys():
			dic[string[depth]] = insert(dic[string[depth]], string, depth + 1)
			return dic.copy()
		else:
			dic[string[depth]] = string
			return dic.copy()
	else:
		dic = oldic
		if dic == string:
			return dic
		elif dic[depth] == string[depth]:
			return {dic[depth]: insert(dic, string, depth + 1)}
		else:
			return {dic[depth]: dic, string[depth]: string}
n = int(input())
arr = []
for _ in range(n):
	arr += [input()]
mainarr = [{}]
dic = {}
for i in range(1, n + 1):
	dic = insert(dic, arr[i - 1] + ' ')
	mainarr.append(dic.copy())
q = int(input())
for _ in range(q):
	(r, string) = input().split()
	r = int(r)
	maindic = mainarr[r]
	for depth in range(len(string)):
		if type(maindic) != dict:
			break
		elif string[depth] in maindic.keys():
			maindic = maindic[string[depth]]
		else:
			break
	if type(maindic) != dict:
		print(maindic)
	else:
		lis = [' ', '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']
		while type(maindic) == dict:
			i = ''
			for letter in lis:
				if letter in maindic.keys():
					i = letter
					break
			maindic = maindic[i]
		print(maindic)


class Mynode(object):

	def __init__(self, char):
		self.char = char
		self.children = []
		self.end = False

def add(root, word):
	node = root
	for char in word:
		found = False
		for child in node.children:
			if child.char == char:
				node = child
				found = True
				break
		if not found:
			newNode = Mynode(char)
			node.children.append(newNode)
			node = newNode
	node.end = True

def find(root, prefix):
	ans = ''
	node = root
	for char in prefix:
		found = False
		for child in node.children:
			if child.char == char:
				found = True
				ans += child.char
				node = child
				break
		if not found:
			break
	while not node.end:
		temp = node.children[0]
		for child in node.children:
			if child.char < temp.char:
				temp = child
		node = temp
		ans += temp.char
	return ans
N = int(input())
strings = []
for k in range(N):
	strings.append(input())
Q = int(input())
queries = []
out = []
for k in range(Q):
	queries.append(input().split())
	out.append('')
queries = sorted(enumerate(queries), key=lambda x: int(x[1][0]))
trie = Mynode(None)
ptr = 0
for k in range(Q):
	qry = int(queries[k][1][0])
	while ptr != qry:
		add(trie, strings[ptr])
		ptr += 1
	out[queries[k][0]] = find(trie, queries[k][1][1])
for k in range(Q):
	print(out[k])


n = int(input())
o = []
p = {}
for j in range(n):
	s = input()
	c = p
	for i in s + '1':
		x = [{}, j]
		if 'min' not in c and i != '1':
			c['min'] = i
		elif i != '1' and i < c['min']:
			c['min'] = i
		if i not in c:
			c[i] = x
		c = c[i][0]
q = int(input())
for j in range(q):
	m = input().split()
	n = int(m[0])
	c = p
	x = m[1][0]
	for i in m[1]:
		if i in c and c[i][1] < n:
			print(i, end='')
			c = c[i][0]
			x = i
		else:
			break
	if '1' in c and c['1'][1] < n:
		pass
	else:
		while True:
			if 'min' in c and (not ('1' in c and c['1'][1] < n)):
				if c[c['min']][1] < n:
					print(c['min'], end='')
					c = c[c['min']][0]
				else:
					min = '111'
					for k in c.keys():
						if k != 'min' and c[k][1] < n:
							if min == '111' or min > k:
								min = k
					print(min, end='')
					c = c[min][0]
			else:
				break
	print()


from collections import defaultdict
st = defaultdict(list)
ln = defaultdict(int)
t = int(input())
for ijk in range(0, t):
	s = input().strip()
	n = len(s)
	for i in range(n, -1, -1):
		if ln[s[:i]] == 0:
			st[s[:i]].append([ijk + 1, s])
			ln[s[:i]] += 1
		elif s < st[s[:i]][-1][1]:
			st[s[:i]].append([ijk + 1, s])
			ln[s[:i]] += 1
q = int(input())
for ijk in range(0, q):
	(r, p) = input().strip().split()
	r = int(r)
	l = 0
	final = [[float('inf'), 0]]
	n = len(p)
	for i in range(n, -1, -1):
		l = len(st[p[:i]])
		if l != 0:
			final = st[p[:i]]
		if final[0][0] <= r:
			break
	ans = final[0][1]
	for j in final:
		if j[0] <= r:
			if j[1] < ans:
				ans = j[1]
		else:
			break
	print(ans)


def sheokand2(dic, r, querie):
	curdic = dic
	word = ''
	for i in querie:
		if i in curdic:
			if curdic[i]['rList'][0] < r:
				word += i
				curdic = curdic[i]
			else:
				break
		else:
			break
	result = getrem(r, curdic)
	word += result
	return word

def getrem(r, curdic):
	if curdic['rList'][0] >= r:
		return False
	if 'end' in curdic and curdic['end'] < r:
		return ''
	key = curdic['aList']
	for i in key:
		word = getrem(r, curdic[i])
		if word != False:
			return i + word
	return False

def sortdic(dic):
	dic['aList'] = list(dic['aList'])
	dic['aList'].sort()
	for i in dic['aList']:
		sortdic(dic[i])

def makedic(strings):
	dic = {'rList': [], 'aList': set()}
	for i in range(len(strings)):
		string = strings[i]
		curdic = dic
		curdic['rList'].append(i)
		for j in string:
			curdic['aList'].add(j)
			if j in curdic:
				curdic = curdic[j]
			else:
				curdic[j] = {'rList': [], 'aList': set()}
				curdic = curdic[j]
			curdic['rList'].append(i)
		if 'end' not in curdic:
			curdic['end'] = i
	sortdic(dic)
	return dic
n = int(input())
strings = []
for i in range(n):
	strings.append(input())
dic = makedic(strings)
q = int(input())
for i in range(q):
	(r, querie) = input().split(' ')
	print(sheokand2(dic, int(r), querie))


def findstring(r, p, s):

	def rec1(t, st):
		if st != '' and st[0] in s[t][2]:
			nt = s[t][2][st[0]]
			if s[nt][1] < r:
				(t, n) = rec1(nt, st[1:])
				return (t, n + 1)
		return (t, 0)

	def rec2(t):
		l = [x for x in s[t][2] if s[s[t][2][x]][1] < r]
		m = min(l)
		if m == '.':
			return ''
		return m + rec2(s[t][2][m])
	(t, n) = rec1(0, p)
	return p[:n] + rec2(t)
n = int(input().strip())
s = [('*', 0, {})]
x = 1
for age in range(n):
	t = 0
	w = input() + '.'
	for i in range(len(w)):
		if w[i] not in s[t][2]:
			s[t][2][w[i]] = x
			s.append((w[i], age, {}))
			t = x
			x += 1
		else:
			t = s[t][2][w[i]]
q = int(input().strip())
for case in range(q):
	(r, p) = [i for i in input().strip().split()]
	print(findstring(int(r), p, s))


def findstring(r, p, s):
	z = ''
	lp = len(p)
	f = True
	t = 0
	i = 0
	while i < 12:
		if f and i < lp:
			if p[i] in s[t][2] and s[s[t][2][p[i]]][1] < r:
				z += p[i]
				t = s[t][2][p[i]]
				i += 1
			else:
				f = False
		else:
			l = list(s[t][2])
			l.sort()
			for j in l:
				nt = s[t][2][j]
				if s[nt][1] < r:
					i += 1
					t = nt
					if j == '.':
						return z
					z += j
					break
	assert 0
n = int(input().strip())
s = [('*', 0, {})]
x = 1
for age in range(n):
	t = 0
	w = input() + '.'
	for i in range(len(w)):
		if w[i] not in s[t][2]:
			s[t][2][w[i]] = x
			s.append((w[i], age, {}))
			t = x
			x += 1
		else:
			t = s[t][2][w[i]]
q = int(input().strip())
for case in range(q):
	(r, p) = [i for i in input().strip().split()]
	print(findstring(int(r), p, s))


from string import ascii_lowercase

def main():
	n = int(input())
	trie = dict()
	words = []
	for i in range(n):
		word = input() + '-'
		words.append(word)
		for j in range(len(word) + 1):
			key = word[:j]
			if key not in trie:
				trie[key] = [i, 1]
			else:
				trie[key][1] += 1
	trie[''] = [min(words), n]
	m = int(input())
	for i in range(m):
		(r, word) = input().split()
		r = int(r)
		j = 0
		while True:
			sub = word[:j + 1]
			if sub not in trie:
				break
			if trie[sub][0] >= r:
				break
			j += 1
			if j == len(word):
				break
			if trie[sub][1] == 1:
				break
		ans = word[:j]
		while trie[ans][1] > 1:
			for l in '-' + ascii_lowercase:
				new_ans = ans + l
				if new_ans in trie and trie[new_ans][0] < r:
					ans = new_ans
					break
			else:
				break
		print(words[trie[ans][0]][:-1])
main()


def search(list, r):
	if r < list[0][0]:
		return None
	low = 0
	high = len(list) - 1
	temp = 0
	while high >= low:
		mid = low + high >> 1
		if list[mid][0] == r:
			return list[mid][1]
		elif list[mid][0] < r:
			if high == low:
				return list[mid][1]
			temp = mid
			low = mid + 1
		elif high == low:
			break
		else:
			high = mid - 1
	return list[temp][1]
no_of_strings = int(input())
strings_list = []
d = {0: 'z' * 10}
for i in range(no_of_strings):
	strings_list.append(input())
	d[i + 1] = min(strings_list[i], d[i])
hash_map = {}
for i in range(no_of_strings):
	for j in range(len(strings_list[i])):
		temp = strings_list[i][:j + 1]
		if temp in hash_map:
			if hash_map[temp][-1][-1] > strings_list[i]:
				hash_map[temp].append([i, strings_list[i]])
		else:
			hash_map[temp] = [[i, strings_list[i]]]
no_of_queries = int(input())
for _ in range(no_of_queries):
	(r, p) = input().split()
	r = int(r)
	found = False
	while not found and len(p) > 0:
		if p in hash_map:
			temp = hash_map[p]
			ans = search(temp, r - 1)
			if ans != None:
				print(ans)
				found = True
			else:
				p = p[:-1]
		else:
			p = p[:-1]
	if not found:
		print(d[r])


class TrieNode:

	def __init__(self):
		self.children = [None] * 26
		self.isEndOfWord = False

class Trie:

	def __init__(self):
		self.root = self.getNode()

	def getNode(self):
		return TrieNode()

	def _charToIndex(self, ch):
		return ord(ch) - ord('a')

	def insert(self, key):
		pCrawl = self.root
		length = len(key)
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				pCrawl.children[index] = self.getNode()
			pCrawl = pCrawl.children[index]
		pCrawl.isEndOfWord = True

	def search(self, key):
		pCrawl = self.root
		length = len(key)
		out = ''
		for level in range(length):
			index = self._charToIndex(key[level])
			if pCrawl.children[index]:
				out += chr(index + ord('a'))
				pCrawl = pCrawl.children[index]
			else:
				break
		while not pCrawl.isEndOfWord:
			for i in range(26):
				if pCrawl.children[i]:
					out += chr(i + ord('a'))
					pCrawl = pCrawl.children[i]
					break
		return out
n = int(input())
strings = [0] * n
for i in range(n):
	strings[i] = input()
q = int(input())
queries = [0] * q
outs = [0] * q
for i in range(q):
	(l, t) = input().split()
	l = int(l)
	queries[i] = [l, t, i]
queries.sort()
t = Trie()
inserted = 0
for i in range(q):
	while inserted < queries[i][0]:
		t.insert(strings[inserted])
		inserted += 1
	outs[i] = (queries[i][2], t.search(queries[i][1]))
outs.sort()
for i in outs:
	print(i[1])


import sys
f = sys.stdin
n = int(f.readline())
s = []
sd = []
for i in range(n):
	z = input()
	s.append(z)
	sd.append(z)
q = int(f.readline())
quer = []
for i in range(q):
	(r, p) = input().split()
	quer.append([int(r), p, i])
quer.sort()
arr = {'': s[0]}
sd.sort()
sortord = {}
for j in range(n):
	sortord[sd[j]] = j
c = 0
finalans = {}
for i in range(q):
	while c < quer[i][0]:
		tb = ''
		if sortord[arr[tb]] >= sortord[s[c]]:
			arr[tb] = s[c]
		for k in range(len(s[c])):
			tb += s[c][k]
			if tb not in arr:
				arr[tb] = s[c]
			elif sortord[arr[tb]] >= sortord[s[c]]:
				arr[tb] = s[c]
		c += 1
	tb = ''
	ans = arr[tb]
	for k in range(len(quer[i][1])):
		tb += quer[i][1][k]
		if tb in arr:
			ans = arr[tb]
		else:
			break
	finalans[quer[i][2]] = ans
for i in range(q):
	print(finalans[i])


class TrieNode:

	def __init__(self):
		self.children = [None] * 26
		self.isEndOfWord = False
		self.Min = chr(255)

class Trie:

	def __init__(self):
		self.root = self.getNode()

	def getNode(self):
		return TrieNode()

	def _charToIndex(self, ch):
		return ord(ch) - ord('a')

	def insert(self, key):
		pCrawl = self.root
		length = len(key)
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				pCrawl.children[index] = self.getNode()
			if pCrawl.Min > key[level]:
				pCrawl.Min = key[level]
			pCrawl = pCrawl.children[index]
		pCrawl.isEndOfWord = True

	def FindAns(self, PFix):
		pCrawl = self.root
		i = 0
		Ans = ''
		for level in range(len(PFix)):
			index = self._charToIndex(PFix[level])
			if not pCrawl.children[index]:
				break
			Ans += PFix[level]
			pCrawl = pCrawl.children[index]
			i += 1
		while True:
			if pCrawl.isEndOfWord:
				break
			else:
				Ans += pCrawl.Min
				idx = self._charToIndex(pCrawl.Min)
				pCrawl = pCrawl.children[idx]
		return Ans

def main():
	t = Trie()
	N = int(input())
	StrList = []
	Queries = []
	for i in range(N):
		StrList.append(input())
	Q = int(input())
	Ans = ['' for x in range(Q)]
	for i in range(Q):
		(r, p) = map(str, input().split())
		r = int(r)
		Queries.append((r, i, p))
	Queries.sort()
	(i, j) = (0, 0)
	while i < Q:
		if j == Queries[i][0]:
			Ans[Queries[i][1]] = t.FindAns(Queries[i][2])
			i += 1
		elif j < N:
			t.insert(StrList[j])
			j += 1
	for x in Ans:
		print(x)
main()


import bisect
s = []
d = {}
d2 = {}

def createstr():
	for (j, i) in enumerate(s):
		if i not in d:
			d[i] = [s[j]]
		else:
			bisect.insort(d[i], s[j])
		for k in range(len(i) - 2, -1, -1):
			if i[:k + 1] not in d:
				d[i[:k + 1]] = [s[j]]
			else:
				bisect.insort(d[i[:k + 1]], s[j])
	d[''] = sorted(s)

def solve(p, r):
	for i in range(len(p), -1, -1):
		if p[:i] in d:
			for o in d[p[:i]]:
				if d2[o] < r:
					print(o)
					return
n = int(input())
for i in range(n):
	m = input()
	s.append(m)
	if m not in d2:
		d2[m] = i
createstr()
q = int(input())
for i in range(q):
	(r, p) = input().split()
	r = int(r)
	solve(p, r)


class Node:

	def __init__(self, value, index, next=None, minString=None):
		self.value = value
		self.minString = minString or 'zzzzzzzzzzz'
		self.next = next or set()
		self.index = index

	def __eq__(self, other):
		return isinstance(other, Node) and self.value == other.value and (self.index == other.index)

	def __hash__(self):
		return hash((self.value, self.index))

	def __repr__(self):
		return '{cls}(value={value}, index={index}, minString={minString}, next={next})'.format(cls=self.__class__.__name__, value=self.value, index=self.index, next=self.next, minString=self.minString)

	def add_min_string(self, minString):
		self.minString = min(self.minString, minString)

	def get_node_in_next(self, value, index):
		for nextNode in self.next:
			if nextNode.value == value and nextNode.index == index:
				return nextNode
		return Node(value, index)

	def get_next_node(self, value, index):
		for nextNode in self.next:
			if nextNode.value == value and nextNode.index == index:
				return nextNode
		return None

	def add_to_next(self, node):
		self.next.add(node)

def process_queries(strings, queries):
	answers = {}
	startNode = Node(value='', index=0)
	for (stringId, string) in enumerate(iterable=strings, start=1):
		prev = startNode
		startNode.add_min_string(minString=string)
		for (letterIndex, letter) in enumerate(iterable=string, start=1):
			node = prev.get_node_in_next(value=letter, index=letterIndex)
			node.add_min_string(minString=string)
			prev.add_to_next(node=node)
			prev = node
		if stringId in queries:
			patterns = queries[stringId]
			for pattern in patterns:
				answers[stringId, pattern] = query(tree=startNode, pattern=pattern)
	return answers

def query(tree, pattern):
	node = tree
	prev = node
	for (index, letter) in enumerate(pattern, 1):
		node = node.get_next_node(value=letter, index=index)
		if not node:
			break
		prev = node
	return prev.minString
strings = []
T = int(input())
for _ in range(T):
	s = input()
	strings.append(s)
queryList = []
Q = int(input())
for __ in range(Q):
	(r, pattern) = list(input().split())
	queryList.append((int(r), pattern))
queries = {}
for (index, pattern) in queryList:
	if index in queries:
		queries[index].append(pattern)
	else:
		queries[index] = [pattern]
answers = process_queries(strings=strings, queries=queries)
for q in queryList:
	print(answers[q])


class TrieNode:
	mapping = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}

	def __init__(self):
		self.children = [None] * 26
		self.value = None
		self.terminal = False
		self.terminal_word_index = -1
		self.word_index = -1
		self.word_value = None

	def __setitem__(self, key, item):
		idx = self.mapping[key]
		self.children[idx] = item

	def __getitem__(self, key):
		idx = self.mapping[key]
		return self.children[idx]

class Trie:

	def __init__(self):
		self.root = TrieNode()
		self.word_counter = 0

	def insert(self, key):
		node = self.root
		index_last_char = None
		for (index_c, c) in enumerate(key):
			nextnode = node[c]
			if nextnode:
				node = nextnode
			else:
				index_last_char = index_c
				break
		if index_last_char is not None:
			for c in key[index_last_char:]:
				newnode = TrieNode()
				node[c] = newnode
				node = newnode
				node.value = c
				node.word_index = self.word_counter
		node.terminal = True
		if node.terminal_word_index == -1:
			node.terminal_word_index = self.word_counter
		node.word_value = key
		self.word_counter += 1

	def search_all(self, key, word_index):
		node = self.root
		common_prefix = []
		for c in key:
			next_node = node[c]
			if next_node is None or word_index < next_node.word_index:
				break
			node = next_node
			common_prefix.append(c)
		stack = [node]
		while stack:
			current = stack.pop()
			if current.terminal and word_index >= current.terminal_word_index:
				yield current.word_value
			for child in reversed(current.children):
				if child is None or word_index < child.word_index:
					continue
				stack.append(child)

	def search(self, key, word_index):
		for w in self.search_all(key, word_index):
			return w

def main():
	t = Trie()
	N = int(input())
	for _ in range(N):
		t.insert(input())
	Q = int(input())
	for _ in range(Q):
		query = input().split()
		R = int(query[0])
		P = query[1]
		res = t.search(P, R - 1)
		print(res)
main()


n = int(input())
s = []
fians = '{{{{{{{{{{'
finalans = []
for i in range(n):
	s.append(input())
	if s[i] < fians:
		fians = s[i]
	finalans.append(fians)
best = {}
ans = {}
for i in range(n):
	for k in range(len(s[i])):
		f = 0
		temp = s[i][0:k + 1]
		if temp not in best:
			best[temp] = s[i]
			f = 1
			ans[temp] = []
		elif s[i] < best[temp]:
			best[temp] = s[i]
			f = 1
		if f == 1:
			ans[temp].append(i)
q = int(input())
for i in range(q):
	flag = 0
	kr = input()
	kr = kr.split()
	k = int(kr[0]) - 1
	r = kr[1]
	for j in range(len(r) - 1, -1, -1):
		maybe = -1
		temp = r[0:j + 1]
		if temp in ans:
			li = ans[temp]
		else:
			continue
		if len(li) == 0:
			continue
		low = 0
		up = len(li) - 1
		while low <= up:
			mid = (up + low) // 2
			if low + 1 == up:
				if li[up] <= k and li[up] > maybe:
					maybe = li[up]
					flag = 1
					break
				if li[low] <= k and li[low] > maybe:
					maybe = li[low]
					flag = 1
					break
				break
			if low == up:
				if li[low] <= k and li[low] > maybe:
					maybe = li[low]
					flag = 1
					break
				break
			if li[mid] <= k and li[mid] > maybe:
				maybe = li[mid]
				flag = 1
			if li[mid] < k:
				low = mid
			elif li[mid] > k:
				up = mid
			else:
				break
		if flag == 1:
			print(s[maybe])
			break
	if flag == 0:
		print(finalans[k])


from bisect import bisect
max_p = 10
N = int(input())
lst = []
for _ in range(N):
	lst.append(input())
ans = {}
for p_size in range(max_p + 1):
	for i in range(len(lst)):
		s = lst[i]
		cur_p = s[:p_size]
		if cur_p in ans:
			p_lst = ans[cur_p]
			last_str = lst[p_lst[len(p_lst) - 1]]
			if s < last_str:
				p_lst.append(i)
		else:
			ans[cur_p] = [i]
Q = int(input())
for _ in range(Q):
	(R, P) = input().split()
	R = int(R) - 1
	while True:
		if P in ans:
			cur_lst = ans[P]
			res = bisect(cur_lst, R)
			if res - 1 >= 0:
				print(lst[cur_lst[res - 1]])
				break
		P = P[:-1]


class trieNode:

	def __init__(self):
		self.children = [None] * 26
		self.isEnd = False
		self.count = ''

class Trie:

	def __init__(self):
		self.root = self.getNode()

	def getNode(self):
		return trieNode()

	def _charToindex(self, ch):
		return ord(ch) - ord('a')

	def insert(self, key):
		root1 = self.root
		for i in range(len(key)):
			ind = self._charToindex(key[i])
			if not root1.children[ind]:
				root1.children[ind] = self.getNode()
			if root1.count == '':
				root1.count = key
			elif root1.count > key:
				root1.count = key
			root1 = root1.children[ind]
		if root1.count == '':
			root1.count = key
		elif root1.count > key:
			root1.count = key
		root1.isEnd = True

	def search(self, key):
		root1 = self.root
		for i in range(len(key)):
			ind = self._charToindex(key[i])
			if not root1.children[ind]:
				return False
			root1 = root1.children[ind]
		return root1 != None and root1.isEnd

	def query(self, key):
		root1 = self.root
		for i in range(len(key)):
			ind = self._charToindex(key[i])
			if not root1.children[ind]:
				return root1.count
			root1 = root1.children[ind]
		return root1.count

class setx:

	def __init__(self, a, s, r):
		self.a = a
		self.s = s
		self.r = r
n = int(input())
x = []
for i in range(n):
	x.append(input())
q = int(input())
array = []
for i in range(q):
	a = [j for j in input().split()]
	z = setx(i, a[1], int(a[0]) - 1)
	array.append(z)
array.sort(key=lambda setx: setx.r)
t = Trie()
ans = []
for j in range(q):
	ans.append('')
for i in range(array[0].r + 1):
	t.insert(x[i])
	ans[array[0].a] = t.query(array[0].s)
for i in range(1, len(array)):
	y = array[i].r - array[i - 1].r
	ind = array[i - 1].r + 1
	if y > 0:
		for j in range(y):
			t.insert(x[ind + j])
	ans[array[i].a] = t.query(array[i].s)
for j in ans:
	print(j)


class TrieNode:

	def __init__(self):
		self.children = [None] * 26
		self.is_end_of_word = False
		self.mins = ''

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def _giveInd(self, ch):
		return ord(ch) - ord('a')

	def insert(self, key, l):
		leafs = key
		yo = self.root
		for i in range(l):
			ind = self._giveInd(key[i])
			if yo.children[ind] == None:
				yo.children[ind] = TrieNode()
			if yo.mins == '':
				yo.mins = leafs
			yo.mins = min(yo.mins, leafs)
			yo = yo.children[ind]
		if yo.mins == '':
			yo.mins = leafs
		yo.mins = min(yo.mins, leafs)
		yo.is_end_of_word = True

	def search(self, key, l):
		yo = self.root
		for i in range(l):
			ind = self._giveInd(key[i])
			if yo.children[ind] == None:
				return False
			yo = yo.children[ind]
		return yo != None and yo.is_end_of_word

	def givecount(self, key, l):
		yo = self.root
		for i in range(l):
			ind = self._giveInd(key[i])
			if yo.children[ind] == None:
				return yo.mins
			yo = yo.children[ind]
		if yo == None:
			return yo.mins
		else:
			return yo.mins

class query:

	def __init__(self, r, query, ind):
		self.ind = ind
		self.query = query
		self.r = r
n = int(input())
sarr = []
for i in range(n):
	si = input()
	sarr.append(si)
q = int(input())
qarr = []
for i in range(q):
	yoarr = list(input().split())
	ri = int(yoarr[0]) - 1
	qi = yoarr[1]
	queryy = query(ri, qi, i)
	qarr.append(queryy)
qarr.sort(key=lambda query: query.r)
prev = -1
trie = Trie()
ansarr = []
for i in range(q):
	ansarr.append('')
for i in qarr:
	if i.r > prev:
		for j in range(prev + 1, i.r + 1):
			trie.insert(sarr[j], len(sarr[j]))
			prev = i.r
		ar = trie.givecount(i.query, len(i.query))
		ansarr[i.ind] = ar
	else:
		ar = trie.givecount(i.query, len(i.query))
		ansarr[i.ind] = ar
for i in range(q):
	print(ansarr[i])