Chef of the Year

All submissions for this problem are available.
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 = a_{1}a_{2}...a_{n} is called lexicographically smaller then the string B = b_{1}b_{2}...b_{m} in the following two cases:
 there exists index i ≤ min{n, m} such that a_{j} = b_{j} for 1 ≤ j < i and a_{i} < b_{i};
 A is a proper prefix of B, that is, n < m and a_{j} = b_{j} 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 spaceseparated integers N and M denoting the number of chefs and the number of emails respectively. Each of the following N lines contains two spaceseparated 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 (10^{4})
 1 ≤ M ≤ 100000 (10^{5})
 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 countrywinner 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 countrywinner 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 countrywinner. 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".
Author:  kaushik_iska 
Tester:  anton_lunyov 
Editorial  http://discuss.codechef.com/problems/CVOTE 
Tags  jan13, kaushik_iska, map, simple, sorting 
Date Added:  3122012 
Time Limit:  1.5 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions