Chefs from all over the globe gather each year for an international convention. Each chef represents some country. Please, note that more than one chef can represent a country.
Each of them presents their best dish to the audience. The audience then sends emails to a secret and secure mail server, with the subject being the name of the chef whom they wish to elect as the "Chef of the Year".
You will be given the list of the subjects of all the emails. Find the country whose chefs got the most number of votes, and also the chef who got elected as the "Chef of the Year" (the chef who got the most number of votes).
Note 1
If several countries got the maximal number of votes, consider the country with the lexicographically smaller name among them to be a winner. Similarly if several chefs got the maximal number of votes, consider the chef with the lexicographically smaller name among them to be a winner.
Note 2
The string A = a1a2...an is called lexicographically smaller then the string B = b1b2...bm in the following two cases:
- there exists index i ≤ min{n, m} such that aj = bj for 1 ≤ j < i and ai < bi;
- A is a proper prefix of B, that is, n < m and aj = bj for 1 ≤ j ≤ n.
The characters in strings are compared by their ASCII codes.
Refer to function strcmp in C or to standard comparator < for string data structure in C++ for details.

-----Input-----
The first line of the input contains two space-separated integers N and M denoting the number of chefs and the number of emails respectively. Each of the following N lines contains two space-separated strings, denoting the name of the chef and his country respectively. Each of the following M lines contains one string denoting the subject of the email.

-----Output-----
Output should consist of two lines. The first line should contain the name of the country whose chefs got the most number of votes. The second line should contain the name of the chef who is elected as the "Chef of the Year".

-----Constraints-----
- 1 ≤ N ≤ 10000 (104)
- 1 ≤ M ≤ 100000 (105)
- Each string in the input contains only letters of English alphabets (uppercase or lowercase)
- Each string in the input has length not exceeding 10
- All chef names will be distinct
- Subject of each email will coincide with the name of one of the chefs

-----Example 1-----
Input:
1 3
Leibniz Germany
Leibniz
Leibniz
Leibniz

Output:
Germany
Leibniz

-----Example 2-----
Input:
4 5
Ramanujan India
Torricelli Italy
Gauss Germany
Lagrange Italy
Ramanujan
Torricelli
Torricelli
Ramanujan
Lagrange

Output:
Italy
Ramanujan

-----Example 3-----
Input:
2 2
Newton England
Euclid Greece
Newton
Euclid

Output:
England
Euclid

-----Explanation-----
Example 1. Here we have only one chef Leibniz and he is from Germany. Clearly, all votes are for him. So Germany is the country-winner and Leibniz is the "Chef of the Year".
Example 2. Here we have chefs Torricelli and Lagrange from Italy, chef Ramanujan from India and chef Gauss from Germany. Torricelli got 2 votes, while Lagrange got one vote. Hence the Italy got 3 votes in all. Ramanujan got also 2 votes. And so India got 2 votes in all. Finally Gauss got no votes leaving Germany without votes. So the country-winner is Italy without any ties. But we have two chefs with 2 votes: Torricelli and Ramanujan. But since the string "Ramanujan" is lexicographically smaller than "Torricelli", then Ramanujan is the "Chef of the Year".
Example 3. Here we have two countries with 1 vote: England and Greece. Since the string "England" is lexicographically smaller than "Greece", then England is the country-winner. Next, we have two chefs with 1 vote: Newton and Euclid. Since the string "Euclid" is lexicographically smaller than "Newton", then Euclid is the "Chef of the Year".

Source: codechef | Difficulty: MEDIUM
Tags: Data structures

Implementation


Solutions:
count_per = {}
per = {}
count = {}
s = list(map(int, input().split()))
for i in range(s[0]):
	x = input().split()
	count_per[x[0]] = x[1]
for j in range(s[1]):
	y = input()
	try:
		per[y] += 1
	except:
		per[y] = 1
	try:
		count[count_per[y]] += 1
	except:
		count[count_per[y]] = 1
a = -1
for (i, j) in count.items():
	if a < j:
		a = j
		p = i
	elif a == j:
		if p > i:
			p = i
print(p)
a = -1
for (i, j) in per.items():
	if a < j:
		a = j
		p = i
	elif a == j:
		if p > i:
			p = i
print(p)


a = {}
b = {}
c = {}
indice1 = 0
indice2 = 0
votoParziale = 0
k = 0
(N, M) = input().split()
N = int(N)
M = int(M)
for i in range(N):
	(chiave, valore) = input().split()
	a[chiave] = valore
	b[chiave] = 0
	c[valore] = 0
for j in range(M):
	chef = input()
	votoParziale = b[chef]
	votoParziale += 1
	b[chef] = votoParziale
for i in a.keys():
	votoParziale = c[a[i]]
	c[a[i]] = b[i] + votoParziale
mass = b[list(a.keys())[0]]
indice2 = list(a.keys())[0]
for chiave in a.keys():
	if b[chiave] > mass:
		indice2 = chiave
		mass = b[chiave]
	elif b[chiave] == mass:
		if chiave < indice2:
			indice2 = chiave
mass = c[a[list(a.keys())[0]]]
indice1 = list(c.keys())[0]
for chiave in c.keys():
	if c[chiave] > mass:
		indice1 = chiave
		mass = c[chiave]
	elif c[chiave] == mass:
		if chiave < indice1:
			indice1 = chiave
print(indice1)
print(indice2)


(n, m) = map(int, input().split())
di = {}
for i in range(n):
	(na, co) = input().split()
	di[na] = co
e = {}
p = {}
for i in range(m):
	q = input()
	if q in e:
		e[q] += 1
	else:
		e[q] = 1
	if di[q] in p:
		p[di[q]] += 1
	else:
		p[di[q]] = 1
m1 = max(e.values())
m2 = max(p.values())
l1 = sorted(p)
l2 = sorted(e)
for i in l1:
	if m2 == p[i]:
		print(i)
		break
for i in l2:
	if m1 == e[i]:
		print(i)
		break


(n, m) = map(int, input().split())
d = {}
for _ in range(n):
	(a, b) = input().split()
	if b in d:
		d[b].append(a)
	else:
		d.update({b: [a]})
v = {}
for _ in range(m):
	a = input()
	if a in v:
		v[a] += 1
	else:
		v.update({a: 1})
d1 = {}
for i in d.keys():
	x = 0
	for j in d[i]:
		if j in v:
			x += v[j]
	if x in d1:
		d1[x].append(i)
	else:
		d1.update({x: [i]})
s = sorted(d1, reverse=True)
d1[s[0]].sort()
print(d1[s[0]][0])
v1 = {}
for i in v.keys():
	if v[i] in v1:
		v1[v[i]].append(i)
	else:
		v1.update({v[i]: [i]})
s1 = sorted(v1, reverse=True)
v1[s1[0]].sort()
print(v1[s1[0]][0])


(a, b) = map(int, input().split())
yy = {}
x = {}
p = {}
for i in range(a):
	y = input().split()
	yy[y[0]] = y[1]
	p[y[1]] = 0
for i in range(b):
	y = input()
	p[yy[y]] += 1
	if y in x:
		x[y] += 1
	else:
		x[y] = 1
dd = x.values()
q = []
for i in x:
	if x[i] == max(dd):
		q.append(i)
dq = []
aa = max(p.values())
for i in p:
	if p[i] == aa:
		dq.append(i)
dq.sort()
print(dq[0])
q.sort()
print(q[0])


(n, m) = map(int, input().split())
chefcon = {}
con = {}
chef = {}
for i in range(n):
	s = input().split()
	chefcon[s[0]] = s[1]
counmax = -1
chefmax = -1
for i in range(m):
	na = input()
	country = chefcon[na]
	if country not in con:
		con[country] = 1
	else:
		con[country] += 1
	counmax = max(counmax, con[country])
	if na not in chef:
		chef[na] = 1
	else:
		chef[na] += 1
	chefmax = max(chefmax, chef[na])
contries = ''
for (k, v) in con.items():
	if v == counmax:
		if contries == '':
			contries = k
		elif k < contries:
			contries = k
print(contries)
chefs = ''
for (k, v) in chef.items():
	if v == chefmax:
		if chefs == '':
			chefs = k
		elif k < chefs:
			chefs = k
print(chefs)


(n, m) = map(int, input().split())
chef_info = dict()
cvalue = dict()
covalue = dict()
country_list = []
for i in range(n):
	(chef_name, country) = map(str, input().split())
	chef_info[chef_name] = country
	cvalue[chef_name] = 0
	covalue[country] = 0
for i in range(m):
	s = input()
	cvalue[s] += 1
	covalue[chef_info[s]] += 1
answer1keys = [i for i in covalue]
answer1values = [covalue[i] for i in covalue]
answer2keys = [i for i in cvalue]
answer2values = [cvalue[i] for i in cvalue]
answer1 = []
answer2 = []
for i in range(len(answer1keys)):
	answer1.append([answer1keys[i], answer1values[i]])
for i in range(len(answer2keys)):
	answer2.append([answer2keys[i], answer2values[i]])
answer1.sort(key=lambda x: x[0])
answer1.sort(key=lambda x: x[1], reverse=True)
answer2.sort(key=lambda x: x[0])
answer2.sort(key=lambda x: x[1], reverse=True)
print(answer1[0][0])
print(answer2[0][0])


(x, y) = map(int, input().split())
s = {}
s1 = {}
s2 = {}
for i in range(x):
	(a, b) = input().split()
	s[a] = b
for i in range(y):
	a = input()
	s1[a] = s1.get(a, 0) + 1
	s2[s[a]] = s2.get(s[a], 0) + 1
m1 = max(s2.values())
c = []
for (a, b) in s2.items():
	if b == m1:
		c.append(a)
print(min(c))
r = max(s1.values())
d = []
for (a, b) in s1.items():
	if b == r:
		d.append(a)
print(min(d))


import sys

def prin(a):
	sys.stdout.write(str(a) + '\n')

def input():
	return sys.stdin.readline().strip()
(a, b) = map(int, input().split())
dis = {}
d = {}
c = {}
(k, m) = (0, 0)
for i in range(a):
	(g, h) = map(str, input().split())
	dis[g] = h
for i in range(b):
	s = input()
	d.setdefault(dis[s], 0)
	c.setdefault(s, 0)
	d[dis[s]] += 1
	c[s] += 1
	if k < d[dis[s]]:
		k = d[dis[s]]
		g = dis[s]
	if m < c[s]:
		m = c[s]
		h = s
for i in d:
	if d[i] == k and i < g:
		g = i
for i in c:
	if c[i] == m and i < h:
		h = i
print(g, h, sep='\n')


(akank, pranava) = map(int, input().split())
c_31809 = {}
for i in range(akank):
	a = input().split()
	c_31809[a[0]] = a[1]
v = {}
con = {}
for i in range(pranava):
	a = input()
	if a in v:
		v[a] += 1
	else:
		v[a] = 1
	if c_31809[a] in con:
		con[c_31809[a]] += 1
	else:
		con[c_31809[a]] = 1
wc_31809 = sorted([i for i in v.keys() if v[i] == max(v.values())])
wcon_31809 = sorted([i for i in con.keys() if con[i] == max(con.values())])
print(wcon_31809[0])
print(wc_31809[0])


(a, b) = map(int, input().split())
d = {}
for i in range(a):
	(name, country) = input().split()
	d[name] = country
d1 = {}
d2 = {}
for i in range(b):
	vote = input()
	if vote in d1:
		d1[vote] += 1
	else:
		d1[vote] = 1
	if d[vote] in d2:
		d2[d[vote]] += 1
	else:
		d2[d[vote]] = 1
m1 = max(d2.values())
m2 = max(d1.values())
print(min((x for x in d2 if d2[x] == m1)))
print(min((x for x in d1 if d1[x] == m2)))


(n, k) = map(int, input().split())
(l, r, s) = ({}, {}, {})
for _ in range(n):
	(a, b) = map(str, input().split())
	l[a] = b
for i in range(k):
	j = input()
	if j in r:
		r[j] += 1
	else:
		r[j] = 1
	if l[j] in s:
		s[l[j]] += 1
	else:
		s[l[j]] = 1
(a, b) = (max(s.values()), max(r.values()))
print(min((x for x in s if s[x] == a)))
print(min((x for x in r if r[x] == b)))


(n, k) = map(int, input().split())
l = []
d = {}
e = {}
p = {}
for i in range(n):
	(s, pi) = map(str, input().split())
	d[s] = pi
	p[s] = 0
	e[pi] = 0
for i in range(k):
	s = input()
	p[s] += 1
	e[d[s]] += 1
l = [(i, j) for (i, j) in p.items()]
l.sort(key=lambda x: (x[1], x[0]))
p = [(i, j) for (i, j) in e.items()]
p.sort(key=lambda x: (x[1], x[0]))
c1 = p[len(p) - 1][1]
for (i, j) in p:
	if j == c1:
		print(i)
		break
c1 = l[len(l) - 1][1]
for (i, j) in l:
	if j == c1:
		print(i)
		break


(n, m) = map(int, input().split())
cd = {}
pd = {}
c = {}
for i in range(n):
	(chef, country) = input().split()
	cd[chef] = country
for i in range(m):
	n = input()
	pd[n] = pd.get(n, 0) + 1
	co = cd[n]
	c[co] = c.get(co, 0) + 1
c = sorted(c.items(), key=lambda x: (-x[1], x[0]))
pd = sorted(pd.items(), key=lambda x: (-x[1], x[0]))
print(c[0][0])
print(pd[0][0])


(n, m) = map(int, input().strip().split())
d = {}
for _ in range(n):
	(r, q) = input().strip().split()
	d.update({r: q})
d1 = dict.fromkeys(sorted([d[i] for i in d]), 0)
d2 = dict.fromkeys(sorted([i for i in d]), 0)
for i in range(m):
	r = input().strip()
	d1[d[r]] += 1
	d2[r] += 1
r = max(d1, key=d1.get)
q = max(d2, key=d2.get)
print(r)
print(q)


(n, m) = map(int, input().split())
d = {}
for i in range(n):
	(a, b) = input().split()
	d[a] = b
k = {}
a = {}
for i in range(m):
	b = input()
	if b in k:
		k[b] += 1
	else:
		k[b] = 1
	if d[b] in a:
		a[d[b]] += 1
	else:
		a[d[b]] = 1
ch = max(k.values())
co = max(a.values())
for i in sorted(a):
	if co == a[i]:
		print(i)
		break
for i in sorted(k):
	if ch == k[i]:
		print(i)
		break


from collections import Counter
(n, m) = map(int, input().split())
d = dict()
for _ in range(n):
	(x, y) = input().split()
	d[x] = y
sci = [input() for _ in range(m)]
cou = [d[i] for i in sci]
(cs, cc) = (Counter(sci), Counter(cou))
(ms, mc) = (cs.most_common(1)[0][1], cc.most_common(1)[0][1])
(s, c) = ([], [])
for (k, v) in cs.items():
	if v == ms:
		s.append(k)
for (k, v) in cc.items():
	if v == mc:
		c.append(k)
s.sort()
c.sort()
print(c[0])
print(s[0])


(n, m) = map(int, input().split())
cache = {}
for i in range(n):
	(x, y) = input().split()
	cache[x] = y
ind = {x: 0 for x in cache}
count = {y: 0 for y in cache.values()}
for i in range(m):
	a = input()
	ind[a] += 1
	count[cache[a]] += 1
print(min(list((x for x in count if count[x] == max(count.values())))))
print(min(list((x for x in ind if ind[x] == max(ind.values())))))


(n, m) = map(int, input().split())
name_country = {}
countrys = {}
names = {}
for i in range(n):
	(name, country) = map(str, input().split())
	name_country[name] = country
	countrys[country] = 0
	names[name] = 0
for i in range(m):
	n = input()
	names[n] += 1
	countrys[name_country[n]] += 1
chef = []
ci = []
for name in names:
	c = (names[name], name)
	chef.append(c)
	ci.append(names[name])
d = []
di = []
for country in countrys:
	c = (countrys[country], country)
	d.append(c)
	di.append(countrys[country])
chef.sort()
ci.sort()
d.sort()
di.sort()
i = di.index(d[-1][0])
j = ci.index(chef[-1][0])
print(d[i][1])
print(chef[j][1])


(n, m) = map(int, input().split())
(l, d, k) = ({}, {}, {})
for i in range(n):
	(a, b) = input().split()
	k[a] = b
	l[a] = 0
	d[b] = 0
for u in range(m):
	s = input()
	l[s] += 1
	d[k[s]] += 1
x = 0
r = ''
for i in d:
	if d[i] == x:
		if i < r:
			r = i
	elif d[i] > x:
		x = d[i]
		r = i
x = 0
rr = ''
for i in l:
	if l[i] == x:
		if i < rr:
			rr = i
	elif l[i] > x:
		x = l[i]
		rr = i
print(r)
print(rr)


def main():
	try:
		(N, M) = map(int, input().split())
		participants: dict = {}
		for i in range(N):
			value = input().split()
			chef = value[0]
			country = value[1]
			participants[chef] = country
		votes: list = []
		for i in range(M):
			votes.append(input())
		sol = resolve(participants, votes)
		print(sol[0])
		print(sol[1])
	except EOFError:
		return

def resolve(participants: dict, votes: list):
	winnerCountry: str = ''
	winnerChef: str = ''
	chefVotes: dict[str, int] = {}
	countyVotes: dict[str, int] = {}
	for i in range(len(votes)):
		if votes[i] not in chefVotes:
			chefVotes[votes[i]] = 1
		else:
			chefVotes[votes[i]] += 1
		chef = votes[i]
		country = participants[chef]
		if country not in countyVotes:
			countyVotes[country] = 1
		else:
			countyVotes[country] += 1
	max: int = 0
	for (chef, count) in chefVotes.items():
		if count > max or (count == max and chef < winnerChef):
			max = count
			winnerChef = chef
	maxCountry: int = 0
	for (country, count) in countyVotes.items():
		if count > maxCountry or (count == maxCountry and country < winnerCountry):
			maxCountry = count
			winnerCountry = country
	return [winnerCountry, winnerChef]
main()


(n, m) = map(int, input().split())
chef_dict = {}
country_dict = {}
for i in range(n):
	(chef, country) = input().split()
	chef_dict[chef] = [country, 0]
	country_dict[country] = 0
for i in range(m):
	chef = input()
	chef_dict[chef][1] += 1
	country_dict[chef_dict[chef][0]] += 1
ans_country = ''
ans_chef = ''
for i in country_dict.keys():
	if ans_country == '':
		ans_country = i
	elif country_dict[ans_country] < country_dict[i] or (country_dict[ans_country] == country_dict[i] and ans_country > i):
		ans_country = i
for i in chef_dict.keys():
	if ans_chef == '':
		ans_chef = i
	elif chef_dict[i][1] > chef_dict[ans_chef][1] or (chef_dict[i][1] == chef_dict[ans_chef][1] and ans_chef > i):
		ans_chef = i
print(ans_country)
print(ans_chef)


(n, m) = map(int, input().split())
dic = {}
for i in range(n):
	(x, y) = input().split()
	dic[x] = y
ind = {}
count = {}
for i in range(m):
	a = input()
	if a in ind:
		ind[a] += 1
	else:
		ind[a] = 1
	if dic[a] in count:
		count[dic[a]] += 1
	else:
		count[dic[a]] = 1
m1 = max(count.values())
m2 = max(ind.values())
print(min((x for x in count if count[x] == m1)))
print(min((x for x in ind if ind[x] == m2)))


(n, m) = map(int, input().split())
d1 = {}
for i in range(n):
	(x, y) = map(str, input().split())
	d1[x] = [0, y]
for i in range(m):
	x = input()
	d1[x][0] += 1
ans = [0, 'zzzzzzzzzzzz']
ans2 = {}
for i in d1:
	if d1[i][0] > ans[0]:
		ans[0] = d1[i][0]
		ans[1] = i
	elif int(d1[i][0]) == int(ans[0]):
		if i < ans[1]:
			ans[1] = i
	if d1[i][1] in ans2:
		ans2[d1[i][1]] += d1[i][0]
	else:
		ans2[d1[i][1]] = d1[i][0]
cans = [0, 'zzzzzzzzzzzz']
for i in ans2:
	if ans2[i] > cans[0]:
		cans[0] = ans2[i]
		cans[1] = i
	elif ans2[i] == cans[0] and i < cans[1]:
		cans[1] = i
print(cans[1])
print(ans[1])


(n, m) = map(int, input().split())
cntry = {}
chf = {}
chf2 = {}
cntry2 = {}
for i in range(n):
	(chef, ct) = map(str, input().split())
	cntry2[ct] = 0
	try:
		cntry[ct].update({chef: 0})
	except:
		cntry[ct] = {chef: 0}
	chf[chef] = ct
	chf2[chef] = 0
for i in range(m):
	chef = input()
	cntry[chf[chef]][chef] += 1
	cntry2[chf[chef]] += 1
	chf2[chef] += 1
cntry2 = {k: v for (k, v) in sorted(cntry2.items(), key=lambda item: item[1])}
mx_cntry = list(cntry2.values())[-1]
res_cntry = '{'
for (k, v) in cntry2.items():
	if v == mx_cntry:
		res_cntry = min(k, res_cntry)
chf2 = {k: v for (k, v) in sorted(chf2.items(), key=lambda item: item[1])}
mx_chef = list(chf2.values())[-1]
res_chef = '{'
for (k, v) in chf2.items():
	if v == mx_chef:
		res_chef = min(k, res_chef)
print(res_cntry)
print(res_chef)


def solver(input_dict):
	sorted_d_by_keys = {k: v for (k, v) in sorted(input_dict.items(), key=lambda item: item[0])}
	return list({k: v for (k, v) in sorted(sorted_d_by_keys.items(), key=lambda item: item[1], reverse=True)}.keys())[0]
(n, m) = map(int, input().split())
d_of_chefs_and_nationalities = {}
d_of_votes_to_chefs = {}
d_of_votes_to_countries = {}
for i in range(n):
	(chef, nation) = input().split()
	d_of_chefs_and_nationalities[chef] = nation
	d_of_votes_to_chefs[chef] = 0
	d_of_votes_to_countries[nation] = 0
for i in range(m):
	chef_voted = input()
	d_of_votes_to_chefs[chef_voted] += 1
	d_of_votes_to_countries[d_of_chefs_and_nationalities[chef_voted]] += 1
print(solver(d_of_votes_to_countries))
print(solver(d_of_votes_to_chefs))


(N, M) = [int(i) for i in input().split()]
get_country = {}
for i in range(N):
	(name, country) = input().split()
	get_country[name] = country
country_votes = {}
name_votes = {}
for i in range(M):
	name = input()
	country_votes[get_country[name]] = country_votes.get(get_country[name], 0) + 1
	name_votes[name] = name_votes.get(name, 0) + 1
win_country = None
votes = -float('inf')
for (i, j) in country_votes.items():
	if j > votes:
		win_country = i
		votes = j
	elif j == votes and i < win_country:
		win_country = i
win_name = None
votes = -float('inf')
for (i, j) in name_votes.items():
	if j > votes:
		win_name = i
		votes = j
	elif j == votes and i < win_name:
		win_name = i
print(win_country)
print(win_name)


(n, m) = map(int, input().split())
d = {}
for i in range(n):
	(ch, co) = input().split()
	d[ch] = co
dch = dict.fromkeys(sorted([i for i in d]), 0)
dco = dict.fromkeys(sorted([d[i] for i in d]), 0)
for i in range(m):
	ans = input()
	dch[ans] += 1
	dco[d[ans]] += 1
print(max(dco, key=dco.get))
print(max(dch, key=dch.get))


import heapq as heap
(n, m) = map(int, input().split())
name_country = {}
name = {}
country = {}
for i in range(n):
	(na, cou) = input().split()
	name_country[na] = cou
for i in range(m):
	s = input()
	cou = name_country[s]
	if s in name:
		name[s] += 1
	else:
		name[s] = 1
	if cou in country:
		country[cou] += 1
	else:
		country[cou] = 1
(countryWinner, chef) = ([], [])
heap.heapify(countryWinner)
heap.heapify(chef)
for (x, y) in name.items():
	heap.heappush(chef, [-y, x])
for (x, y) in country.items():
	heap.heappush(countryWinner, [-y, x])
print(heap.heappop(countryWinner)[1], heap.heappop(chef)[1], sep='\n')


(n, m) = map(int, input().split())
d = {}
for i in range(0, n):
	(chef, country) = input().split()
	d[chef] = country
d2 = dict.fromkeys(sorted([i for i in d]), 0)
d1 = dict.fromkeys(sorted([d[i] for i in d]), 0)
for i in range(0, m):
	mail = input()
	d2[mail] = d2[mail] + 1
	d1[d[mail]] += 1
ans1 = max(d1, key=d1.get)
ans2 = max(d2, key=d2.get)
print(ans1)
print(ans2)


(n, m) = [int(x) for x in input().split(' ')]
d1 = {}
for _ in range(n):
	(s1, s2) = [str(x) for x in input().split(' ')]
	d1[s1] = s2
d2 = {}
d3 = {}
for _ in range(m):
	s1 = input()
	if d1[s1] in d2:
		d2[d1[s1]] += 1
	else:
		d2[d1[s1]] = 1
	if s1 in d3:
		d3[s1] += 1
	else:
		d3[s1] = 1
con_vote = max(d2.values())
chef_vote = max(d3.values())
temp = 'zzzzzzzzzzz'
for i in d2:
	if d2[i] == con_vote and i < temp:
		temp = i
print(temp)
temp = 'zzzzzzzzzzz'
for i in d3:
	if d3[i] == chef_vote and i < temp:
		temp = i
print(temp)


(n, k) = map(int, input().split())
top_chef = {}
contry = {}
top_cont = {}
for _ in range(n):
	(chef, cont) = input().split()
	contry[chef] = cont
for _ in range(k):
	chef = input()
	cont = contry[chef]
	try:
		top_chef[chef] += 1
	except:
		top_chef[chef] = 1
	try:
		top_cont[cont] += 1
	except:
		top_cont[cont] = 1
cont_ans = sorted(list(top_cont.items()), key=lambda x: [-x[1], x[0]], reverse=True)
chef_ans = sorted(list(top_chef.items()), key=lambda x: [-x[1], x[0]], reverse=True)
print(cont_ans[-1][0])
print(chef_ans[-1][0])


(m, n) = map(int, input().split())
c = {}
for i in range(m):
	a = input().split()
	c[a[0]] = a[1]
v = {}
con = {}
for i in range(n):
	a = input()
	if a in v:
		v[a] += 1
	else:
		v[a] = 1
	if c[a] in con:
		con[c[a]] += 1
	else:
		con[c[a]] = 1
wc = sorted([i for i in v.keys() if v[i] == max(v.values())])
wcon = sorted([i for i in con.keys() if con[i] == max(con.values())])
print(wcon[0])
print(wc[0])


from sys import stdin
from math import log, floor, ceil, gcd
from collections import defaultdict as dd
input = stdin.readline
inp = lambda : int(stdin.readline())
rs = lambda : stdin.readline().strip()

def ra(typ):
	return list(map(typ, stdin.readline().split()))

def rv(typ):
	return map(typ, stdin.readline().split())

def main():
	(n, m) = rv(int)
	ch_con = {}
	con = dd(int)
	ch = dd(int)
	for _ in range(n):
		x = ra(str)
		ch_con[x[0]] = x[1]
	for _ in range(m):
		x = rs()
		ch[x] += 1
		con[ch_con[x]] += 1
	country = 'zzzzzzzzzz'
	c = 0
	for i in con:
		if con[i] > c:
			country = i
			c = con[i]
		elif con[i] == c:
			if i < country:
				country = i
	chef = 'zzzzzzzzzz'
	c = 0
	for i in ch:
		if ch[i] > c:
			chef = i
			c = ch[i]
		elif ch[i] == c:
			if i < chef:
				chef = i
	print(country)
	print(chef)
main()


import os, sys, io, math
from array import array
from math import *
from bisect import *
from heapq import *
from functools import *
from itertools import *
from collections import Counter, defaultdict
I = lambda : [*map(int, sys.stdin.readline().split())]
IS = lambda : input()
IN = lambda : int(input())
IF = lambda : float(input())
(n, k) = map(int, input().split())
(l, r, s) = ({}, {}, {})
for _ in range(n):
	(a, b) = map(str, input().split())
	l[a] = b
for i in range(k):
	j = IS()
	if j in r:
		r[j] += 1
	else:
		r[j] = 1
	if l[j] in s:
		s[l[j]] += 1
	else:
		s[l[j]] = 1
(a, b) = (max(s.values()), max(r.values()))
print(min((x for x in s if s[x] == a)))
print(min((x for x in r if r[x] == b)))


(a, b) = map(int, input().split())
d = {}
for i in range(a):
	(che, cou) = input().split()
	d.update({che: cou})
ch = {}
co = {}
for i in range(b):
	q = input()
	if q in ch.keys():
		ch.update({q: ch[q] + 1})
	else:
		ch.update({q: 1})
	s = d[q]
	if s in co.keys():
		co.update({s: co[s] + 1})
	else:
		co.update({s: 1})
ma = 0
h = {}
o = {}
for (i, j) in ch.items():
	if j > ma:
		h.clear()
		h.update({j: [i]})
		ma = j
	elif j == ma:
		h[j].append(i)
		h[j].sort()
maa = 0
for (i, j) in co.items():
	if j > maa:
		o.clear()
		o.update({j: [i]})
		maa = j
	elif j == maa:
		o[j].append(i)
		o[j].sort()
for i in o.values():
	print(i[0])
for i in h.values():
	print(i[0])


from collections import defaultdict
chef_country = defaultdict(str)
country = defaultdict(int)
name = defaultdict(int)
(a, b) = list(map(int, input().split()))
(c, n) = (0, 0)
(country_name, chef_name) = ([], [])
for i in range(a):
	(p, q) = list(map(str, input().split()))
	chef_country[p] = q
for i in range(b):
	q = input()
	country[chef_country[q]] += 1
	name[q] += 1
	if country[chef_country[q]] > c:
		c = country[chef_country[q]]
		country_name = [chef_country[q]]
	elif country[chef_country[q]] == c:
		country_name.append(chef_country[q])
	if name[q] > n:
		n = name[q]
		chef_name = [q]
	elif name[q] == n:
		chef_name.append(q)
country_name.sort()
chef_name.sort()
print(country_name[0])
print(chef_name[0])


(m, n) = map(int, input().split(' '))
(d, chef, country) = ({}, {}, {})
for i in range(m):
	(a, b) = input().split(' ')
	d[a] = b
	chef[a] = 0
	country[b] = 0
for i in range(n):
	x = input()
	chef[x] = chef[x] + 1
	country[d[x]] = country[d[x]] + 1
p = sorted(sorted(chef.items(), key=lambda x: x[0]), key=lambda x: x[1], reverse=True)
q = sorted(sorted(country.items(), key=lambda x: x[0]), key=lambda x: x[1], reverse=True)
print(str(next(iter(q[0]))))
print(str(next(iter(p[0]))))


(n, m) = map(int, input().split())
dict1 = {}
dict2 = {}
dict3 = {}
p = []
q = []
for j in range(n):
	(x, y) = map(str, input().split())
	dict1[x] = y
for j in range(m):
	s = input()
	if s not in dict2:
		dict2[s] = 1
	else:
		dict2[s] += 1
	o = dict1[s]
	if o not in dict3:
		dict3[o] = 1
	else:
		dict3[o] += 1
r = 0
b_chef = ''
for (k, i) in dict2.items():
	if r < i:
		r = i
		b_chef = k
for (k, i) in dict2.items():
	if r == i:
		p.append(k)
p.sort()
l = 0
b_c = ''
for (k, i) in dict3.items():
	if l < i:
		l = i
		b_c = k
for (k, i) in dict3.items():
	if l == i:
		q.append(k)
q.sort()
print(q[0])
print(p[0])


(n, m) = map(int, input().split())
chef_map = {}
coun_map = {}
for i in range(n):
	(chef, coun) = map(str, input().split())
	chef_map[chef] = [0, coun]
	coun_map[coun] = 0
for mail in range(m):
	c = str(input())
	chef_map[c][0] += 1
	coun_map[chef_map[c][1]] += 1
coun_map = dict(sorted(coun_map.items(), key=lambda x: x[0], reverse=True))
coun_map = dict(sorted(coun_map.items(), key=lambda x: x[1]))
chef_map = dict(sorted(chef_map.items(), key=lambda x: x[0], reverse=True))
chef_map = dict(sorted(chef_map.items(), key=lambda x: x[1][0]))
x = list(coun_map.items())[-1]
y = list(chef_map.items())[-1]
print(x[0])
print(y[0])


(y, m) = map(int, input().split())
d = {}
for j in range(y):
	(c, h) = input().split()
	d[c] = h
v = {}
for j in range(m):
	c = input()
	if c in v:
		v[c] += 1
	else:
		v[c] = 1
cv = {}
w = 0
for j in v:
	if d[j] in cv:
		cv[d[j]] += v[j]
	else:
		cv[d[j]] = v[j]
	if cv[d[j]] > w:
		w = cv[d[j]]
		wc = d[j]
	elif cv[d[j]] == w:
		if d[j] < wc:
			wc = d[j]
print(wc)
wv = 0
for j in v:
	if v[j] > wv:
		wv = v[j]
		wc = j
	elif v[j] == wv:
		if j < wc:
			wc = j
print(wc)


(n, m) = map(int, input().split())
d = {}
for j in range(n):
	(c, con) = input().split()
	d[c] = con
v = {}
for j in range(m):
	c = input()
	if c in v:
		v[c] += 1
	else:
		v[c] = 1
cv = {}
w = 0
for j in v:
	if d[j] in cv:
		cv[d[j]] += v[j]
	else:
		cv[d[j]] = v[j]
	if cv[d[j]] > w:
		w = cv[d[j]]
		wc = d[j]
	elif cv[d[j]] == w:
		if d[j] < wc:
			wc = d[j]
print(wc)
wv = 0
for j in v:
	if v[j] > wv:
		wv = v[j]
		wc = j
	elif v[j] == wv:
		if j < wc:
			wc = j
print(wc)