Problem Classification

Interview

Time limit1sMemory limit512 MB

Summary

Count exact whole-word occurrences of each category's keywords in a statement, then print the categories with the highest total count in lexicographic order.

Level: Medium4 of 10
Topics: Hash map, String, Implementation, Sorting
Solved: No attempts yet

Problem

When reading programming problems, one can often get hints about the topic of a problem by skimming the problem statement for certain words. If, for example, the word "vertex" or "edge" appears, the problem is almost certainly a graph problem, while the words "words" or "letters" suggest that the problem is about strings.

Your task is to implement a simple program that attempts to classify a problem according to one of $N$ categories. Each category has an associated set of words, which, if they appear as words in a statement, suggest the problem belongs to this category. When classifying a statement, the program should suggest those categories which have the highest number of occurrences of their associated words. Note that words that are part of other words do not count. For example, the word statement should not count as an occurrence for the word ate.

In the above example, we suggested that the category graph may have the associated words vertex and edge and the category string could have the associated words words and letters. Then, if there were $3$ occurrences each of the words vertex and edge, the number of matches for the category graph would be $6$ . If the statement contained $14$ occurrences of words and $4$ of letters, the number of matches for the category string would be $18$ . Since there are more matches for the second category, the program should suggest it.

If there are multiple categories with the same number of matches, your program should suggest all of them.

Input

The first line of input contains the number of categories $1 \le N \le 10$ .

The next $N$ lines each contain a description of a category. The description starts with the name of the category, a single word. Then, an integer $1 \le W \le 10$ follows, which is the number of words associated with this category. This is followed by those $W$ words, separated by spaces. No two words within a category are the same, and no two categories have the same name.

This is followed by a number of lines describing the statement of the problem. Each line contains a list of space-separated words.

Every word in the input will consist solely of at most $30$ lower-case letters a-z. The statement consists of between $1$ and $10\,000$ words.

Output

For each suggested category, output the name of the category on a single line, in lexicographical order.

Examples2

Example 1

Input

4
datastructure 3 query range sum
geometry 3 euclid range vertex
graph 3 query vertex hamiltonian
math 3 hamiltonian sum euclid
consider the hamiltonian graph where each vertex corresponds
to an linear equation we can solve these using the euclid
algorithm now you will receive a query corresponding to a
range of vertices your task is to compute the sum of the
minimum solution of those vertices

Expected output

datastructure
geometry
graph
math

Example 2

Input

2
graph 2 vertex edge
string 2 words letters
problem classification
when reading programming problems one can often get some
hints regarding the topic of the problem by skimming the
problem statement for certain words if for example the
word vertex or edge appears the problem is almost
certainly a graph problem while the words words or
letters suggest that the problem is about strings your
task is to implement a simple program that attempts to
classify a problem according to one of n categories each
category has an associated set of words which if they
appear as words in a statement suggest the problem
belongs to this category when classifying a statement
the program should suggest those categories which have
the highest number of occurences of their associated
words in the above example we suggested that the
category graph may have the associated words vertex
and edge and the category string could have the
associated words words and letters then if there were
occurances each of the words vertex and edge the number
of matches for the category graph would be if the
statement contained occurances of words and of letters
the number of matches for the category string would be 
since there are more matches for the second category
the program should suggest it if there are multiple
categories with the same number of matches your
program should suggest all of them
input
the first line of input contains the number of categories
n the next n lines each contain a description of a
category the description starts with the name of the
category a single word then an integer w follows 
the number of words associated with this category this
is followed by those w words separated by spaces this
is followed by a number of lines describing the
statement of the problem each line contains a list of
spaceseparated words every word in the input will
consist solely of lowercase letters a z output for each
suggested category output the name of the category on a
single line in lexicographical order

Expected output

string