Chef Jessie has a lot of recipes with her (N). She often remembered the starting few characters of the recipe and forgot the rest. As all the great chefs do, Jessie also numbered the recipes depending on the priority. So, given the list of recipes along with their priorities answer Jessie’s queries.
Jessie’s queries are as follows:

She gives you the first few characters of a recipe; you have to print the complete recipe with the highest priority.
Note:

Every recipe has a unique priority

-----Input-----

First line contains an integer N - the number of recipes.

Followed by N strings Si along with an integer each Vi.
Si stands for the recipe and Vi for the priority.

It is followed by an integer Q - the number of queries.

Followed by Q strings Qi.

Each string Si, Qi contain only lowercase Latin alphabets ('a' - 'z') and '-'.

-----Output-----
Q – lines, each contain the answer for each of the query.

If for a query no recipe matches print "NO". (Without quotes)
Constraints:
0 <= N <= 1000

0 <= Q <= 1000

-10^9 <= Vi <= 10^9

1 <= |Si| <= 1000 (length of Si)

1 <= |Qi| <= 1000 (length of Qi)

-----Example-----
Input:
4
flour-with-eggs 100
chicken-ham -10
flour-without-eggs 200
fish-with-pepper 1100
6
f
flour-with
flour-with-
c
fl
chik

Output:
fish-with-pepper
flour-without-eggs
flour-with-eggs
chicken-ham
flour-without-eggs
NO

Difficulty: MEDIUM
Tags: String algorithms

Data structures

Complete search
Skill types: Data structures

Complete search

Starter code:

Solutions:
n = int(input())
s = []
a = []
for i in range(n):
	(si, vi) = input().split()
	vi = int(vi)
	a.append(vi)
	s.append(si)
q = int(input())
for j in range(0, q):
	qi = input()
	ma = -20000000009
	pos = -1
	for k in range(0, n):
		if s[k].startswith(qi):
			if a[k] > ma:
				pos = k
				ma = a[k]
	if pos == -1:
		print('NO')
	else:
		print(s[pos])


def twstr():
	recipes = dict()
	for n in range(int(input())):
		(recipe, priority) = input().strip().split()
		priority = int(priority)
		recipes[priority] = recipe
	for q in range(int(input())):
		start = input().strip()
		recipe = 'NO'
		for prio in sorted(recipes.keys(), reverse=True):
			if recipes[prio].startswith(start):
				recipe = recipes[prio]
				break
		print(recipe)
twstr()


N = int(input())
dic = {}
for i in range(N):
	(s, v) = input().split()
	v = int(v)
	dic[s] = v
for i in range(int(input())):
	S = input()
	m = -20000000009
	q = ''
	for (i, j) in dic.items():
		if i[:len(S)] == S:
			if j > m:
				q = i
				m = j
	if len(q) == 0:
		print('NO')
	else:
		print(q)


import re
n = int(input())
l = []
for _ in range(n):
	l.append(input().split())
	l[-1][1] = int(l[-1][1])
l.sort(key=lambda x: x[1], reverse=True)
q = int(input())
for _ in range(q):
	s = '^' + input()
	for k in l:
		if re.findall(s, k[0]):
			print(k[0])
			break
	else:
		print('NO')


n = int(input())
li = []
for i in range(n):
	(string, pri) = input().split()
	pri = int(pri)
	li.append([string, pri])
li.sort(key=lambda x: x[1], reverse=True)
q = int(input())
for i in range(q):
	start = input()
	f = 0
	for i in range(n):
		if li[i][0].startswith(start):
			f = 1
			print(li[i][0])
			break
	if not f:
		print('NO')


n = int(input())
a = []
b = []
for _ in range(n):
	s = input().split()
	a.append(s[0])
	b.append(int(s[1]))
q = int(input())
for i in range(q):
	x = input()
	m = -10 ** 10
	for k in range(n):
		y = a[k]
		if x in y and x == y[0:len(x)]:
			m = max(m, b[k])
	if m == -10 ** 10:
		print('NO')
	else:
		j = b.index(m)
		print(a[j])


r = []
for _ in range(int(input())):
	(s, i) = input().split()
	r.append((s, int(i)))
r = sorted(r, key=lambda x: x[1], reverse=True)
for _ in range(int(input())):
	inp = input()
	done = 0
	for (s, i) in r:
		if s[:len(inp)] == inp:
			print(s)
			done = 1
			break
	if not done:
		print('NO')


S = []
for _ in range(int(input())):
	(s, v) = input().split()
	v = int(v)
	S.append([v, s])
S.sort(reverse=True)
for _ in range(int(input())):
	s = input()
	found = False
	for i in range(len(S)):
		if S[i][1].find(s) == 0:
			print(S[i][1])
			found = True
			break
	if not found:
		print('NO')


class Recipe:

	def __init__(self, text, priority):
		self.text = text
		self.priority = priority
N = int(input())
recipes = []
for n in range(N):
	line = input().split()
	recipes.append(Recipe(line[0], int(line[1])))
recipes.sort(key=lambda a: a.priority, reverse=True)
Q = int(input())
output = []
for q in range(Q):
	recipe_text = input()
	recipe_index = -1
	for r in range(len(recipes)):
		if recipes[r].text.startswith(recipe_text):
			recipe_index = r
			break
	if recipe_index == -1:
		output.append('NO')
	else:
		output.append(recipes[recipe_index].text)
print('\n'.join(output))


nr = int(input())
d = {}
for r in range(nr):
	(s, v) = map(str, input().split())
	d[int(v)] = s
q = int(input())
lis = []
for i in range(q):
	lis.append(input())
l = list(d.keys())
l.sort(reverse=True)
ans = 'NO'
for j in lis:
	ans = 'NO'
	for k in l:
		if len(j) <= len(d[k]):
			a = d[k]
			if j == a[0:len(j)]:
				ans = a
				break
	print(ans)


n = int(input())
d = dict()
for _ in range(n):
	aa = input().split()
	s = aa[0]
	v = int(aa[1])
	d[s] = v
q = int(input())
for _ in range(q):
	qi = input()
	value = None
	recep = None
	for i in d:
		if i.startswith(qi):
			if value is None or value < d[i]:
				value = d[i]
				recep = i
	if recep == None:
		print('NO')
	else:
		print(recep)


n = int(input())
recipe = []
for _ in range(n):
	(si, vi) = map(str, input().split())
	recipe.append([si, int(vi)])
recipe.sort(key=lambda x: x[1], reverse=True)
for i in range(int(input())):
	q = input()
	for j in range(len(recipe)):
		if q == recipe[j][0][:len(q)]:
			print(recipe[j][0])
			break
	else:
		print('NO')


n = int(input())
recipes = {}
for i in range(n):
	(recipe, priority) = input().split()
	priority = int(priority)
	recipes[recipe] = priority
q = int(input())
for i in range(q):
	query = input().strip()
	max_priority = -10 ** 9 - 1
	max_recipe = 'NO'
	for recipe in recipes:
		if recipe.startswith(query) and recipes[recipe] > max_priority:
			max_priority = recipes[recipe]
			max_recipe = recipe
	print(max_recipe)


res = []
for _ in range(int(input())):
	(a, b) = map(str, input().split())
	res.append([a, int(b)])
res.sort(key=lambda x: x[-1])
for _ in range(int(input())):
	check = input().strip()
	f = 1
	for i in range(len(res) - 1, -1, -1):
		if res[i][0][:len(check)] == check:
			f = 0
			ans = res[i][0]
			break
	if f == 1:
		print('NO')
	elif f == 0:
		print(ans)


di = {}
li = []
lis = []
for i in range(int(input())):
	(s, n) = map(str, input().split())
	di[n] = s
	li.append(int(n))
li.sort(reverse=True)
for i in li:
	lis.append(di[str(i)])
for i in range(int(input())):
	q = input()
	for j in range(len(lis)):
		if q in lis[j] and q == lis[j][0:len(q)]:
			print(lis[j])
			break
	else:
		print('NO')


a = int(input())
b = []
for _ in range(a):
	aa = input().split()
	b.append((aa[0], int(aa[1])))
b = sorted(b, key=lambda x: x[1], reverse=True)
ab = int(input())
for i in range(ab):
	cc = input()
	for i in b:
		if len(cc) <= len(i[0]) and i[0][:len(cc)] == cc:
			print(i[0])
			break
	else:
		print('NO')


N = int(input())
temp_list = []
for i in range(N):
	(r, p) = input().split()
	temp_list.append((r, int(p)))
rec_list = sorted(temp_list, key=lambda lis: lis[1], reverse=True)
Q = int(input())
for i in range(Q):
	current_rec = 'NO'
	current_rec_pri = -10 ** 9
	sfc = input()
	sfc_len = len(sfc)
	for j in range(N):
		rec = rec_list[j][0]
		rec_pri = rec_list[j][1]
		if sfc == rec[:sfc_len] and rec_pri >= current_rec_pri:
			current_rec = rec
			current_rec_pri = rec_pri
			break
	print(current_rec)


def keyFn(tp):
	return tp[1]
n = int(input())
recipes = []
i = 0
while i < n:
	line = input().split()
	recipes.append((line[0], int(line[1])))
	i += 1
q = int(input())
i = 0
srec = sorted(recipes, key=keyFn, reverse=True)
while i < q:
	name = input()
	ans = 'NO'
	for items in srec:
		if items[0].startswith(name):
			ans = items[0]
			break
	print(ans)
	i += 1


n = int(input())
slist = []
plist = []
while n > 0:
	n = n - 1
	(s, p) = input().split()
	slist.append(s)
	plist.append(p)
r = int(input())
while r > 0:
	r = r - 1
	c = -10000000000
	flag = 0
	s1 = input()
	for i in range(len(slist)):
		dummy = slist[i]
		v = dummy.find(s1)
		if v == 0:
			if int(c) < int(plist[i]):
				dummy1 = dummy
				c = plist[i]
				flag = 1
	if flag == 1:
		print(dummy1)
	else:
		print('NO')


import sys
input = sys.stdin.readline

def rii():
	return range(int(input().strip()))

def ii():
	return int(input().strip())

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

def lmii():
	return list(map(int, input().strip().split(' ')))

def si():
	return str(input().strip())
from operator import itemgetter
failure = 'NO'

class Recipe(dict):

	def starts_with(self, start_of_key):
		return sorted([(key, self[key]) for key in self if key.startswith(start_of_key)], reverse=True, key=itemgetter(1))

def solve(*args):
	(r, starts) = args
	for s in starts:
		ss = r.starts_with(s)
		if len(ss) > 0:
			print(ss[0][0])
		else:
			print(failure)

def do_codechef():
	n = ii()
	r = Recipe()
	for _ in range(n):
		(x, y) = input().split(' ')
		r[x] = int(y.strip())
	q = ii()
	starts = [input().strip() for x in range(q)]
	solve(r, starts)
do_codechef()
exit()


recipes = int(input())
recipes_dict = {}
for i in range(recipes):
	(recipe, priority) = input().split()
	recipes_dict[recipe] = int(priority)
queries = int(input())
for i in range(queries):
	query = input()
	ans = 'NO'
	priority = -10 ** 9 - 1
	for j in recipes_dict:
		if j.startswith(query) and recipes_dict[j] > priority:
			ans = j
			priority = recipes_dict[j]
	print(ans)


numrec = int(input())
reclst = {}
recval = []
for i in range(numrec):
	(p, s) = input().split(' ')
	reclst.update({s: p})
querynum = int(input())
for j in range(querynum):
	query = input()
	recval = [int(key) for (key, value) in reclst.items() if value.startswith(query)]
	recval.sort(reverse=True)
	try:
		value1 = recval[0]
		print(reclst.get(str(value1)))
		recval.clear()
	except:
		print('NO')


import sys
import math
from time import time
from itertools import permutations, combinations
import collections
import functools
from fractions import gcd, Fraction
import string
import operator
import bisect

class timed(object):

	def __init__(self, func):
		self.func = func

	def __call__(self, *args):
		t1 = time()
		ret = self.func(*args)
		dif_time = time() - t1
		print('%s: returned %s in %f seconds' % (self.func.__name__, ret, dif_time))
		return ret

def comp(f1, f2, *args):
	t1 = time()
	r1 = f1(*args) if f1 is not None else None
	t2 = time()
	r2 = f2(*args) if f2 is not None else None
	t3 = time()
	res = '%5s: %s in %f\n%5s: %s in %f' % (f1.__name__ if f1 is not None else None, r1, t2 - t1, f2.__name__ if f2 is not None else None, r2, t3 - t2)
	if r1 != r2:
		dr = '!! DIFFERENT RESULTS !!'
		res = dr + '\n' + res + '\n' + dr
	print(res)

def alg():
	return 0

def main():
	data = sys.stdin
	nb = int(data.readline())
	recipes = []
	for i in range(nb):
		(name, prio) = data.readline().split()
		recipes.append((name, int(prio)))
	recipes = [r for (r, p) in sorted(recipes, key=operator.itemgetter(1), reverse=True)]
	nb = int(data.readline())
	for icase in range(nb):
		q = data.readline().strip()
		found = False
		for r in recipes:
			if r.startswith(q):
				print(r)
				found = True
				break
		if not found:
			print('NO')
main()


import sys
t = int(input())
list1 = []
for _ in range(t):
	s = input()
	n = len(s)
	num = ''
	for i in range(len(s)):
		if s[n - i - 1] == ' ':
			list1.append([s[0:n - i - 1], int(num)])
			break
		else:
			num = s[n - i - 1] + num
n = int(input())
for _ in range(n):
	s = input()
	x = len(s)
	temp = 0
	s_final = ''
	j = 0
	min_num = -1 * sys.maxsize
	for j in range(t):
		y = list1[j][0]
		for i in range(x):
			if s[i] == y[i]:
				temp = temp + 1
			else:
				break
		if temp == x and min_num < list1[j][1]:
			min_num = list1[j][1]
			s_final = y
		temp = 0
	if min_num == -1 * sys.maxsize:
		print('NO')
	else:
		print(s_final)


cookbook = dict()
for i in range(int(input())):
	foo = input().split()
	priority = int(foo[1])
	cookbook[priority] = foo[0]
it = [cookbook[i] for i in sorted(cookbook, reverse=True)]
for i in range(int(input())):
	prefix = input().rstrip()
	for j in it:
		if j.startswith(prefix):
			print(j)
			break
	else:
		print('NO')


n = int(input())
l = []
while n > 0:
	n -= 1
	(k, v) = input().split(' ')
	v = int(v)
	l.append([k, v])
q = int(input())
while q > 0:
	q -= 1
	s = input()
	max = -1000000001
	ans = ''
	for (k, v) in l:
		if k.startswith(s) and v > max:
			max = v
			ans = k
	if ans == '':
		print('NO')
	else:
		print(ans)


class TrieNode:

	def __init__(self):
		self.children = [None] * 27
		self.ispresent = 0
		self.priority = 'aa'
		self.index = -1

class Trie:

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

	def getnode(self):
		return TrieNode()

	def getind(self, ch):
		if ch == '-':
			return 26
		return ord(ch) - 97

	def insert(self, key, pos, pri):
		curr = self.root
		l = len(key)
		for i in range(l):
			place = self.getind(key[i])
			if curr.children[place] == None:
				curr.children[place] = self.getnode()
				curr = curr.children[place]
				curr.index = pos
				curr.priority = pri
			else:
				curr = curr.children[place]
				if pri > curr.priority:
					curr.priority = pri
					curr.index = pos
		curr.ispresent = 1

	def search(self, key):
		curr = self.root
		l = len(key)
		for i in range(l):
			place = self.getind(key[i])
			if curr.children[place] == None:
				return -1
			curr = curr.children[place]
		return curr.index
data = Trie()
n = int(input())
strings = []
for i in range(n):
	(string, pri) = input().split()
	pri = int(pri)
	data.insert(string, i, pri)
	strings.append(string)
q = int(input())
for i in range(q):
	start = input()
	ans = data.search(start)
	if ans == -1:
		print('NO')
	else:
		print(strings[ans])


class trienode:

	def __init__(self):
		self.children = [None] * 27
		self.ispresent = 0
		self.priority = 'aa'
		self.index = -1

class trie:

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

	def getnode(self):
		return trienode()

	def getindex(self, ch):
		if ch != '-':
			return ord(ch) - ord('a')
		else:
			return 26

	def insert(self, key, pos, pri):
		current = self.root
		l = len(key)
		for i in range(l):
			place = self.getindex(key[i])
			if current.children[place] == None:
				current.children[place] = self.getnode()
				current = current.children[place]
				current.index = pos
				current.priority = pri
			else:
				current = current.children[place]
				if current.priority < pri:
					current.priority = pri
					current.index = pos
		current.ispresent = 1

	def search(self, key):
		current = self.root
		l = len(key)
		for i in range(l):
			place = self.getindex(key[i])
			if current.children[place] == None:
				return -1
			current = current.children[place]
		return current.index
data = trie()
n = int(input())
strs = []
for i in range(n):
	temp = list(input().split())
	s = temp[0].strip()
	val = int(temp[1])
	data.insert(s, i, val)
	strs.append(s)
q = int(input())
for i in range(q):
	s = input()
	ans = data.search(s)
	if ans == -1:
		print('NO')
	else:
		print(strs[ans])