Description

There are many different ethnic groups in Yugo. In total there are $N$ different languages, but the chairperson threw you a few dictionaries, so now you can understand what they are speaking. Your task is to determine which language they are speaking and fill it in the register.

Specifically, you are given the names of $N$ languages and several known words from each language. It is guaranteed that each word appears in at most one language. You are also given several sentences. For each sentence, you need to determine which language it belongs to (word matching is case-insensitive).

A sentence is a string that contains only uppercase and lowercase letters, spaces, -, ', ., ,, ?, !, ;, ( and ), among which, and only among which, space, ., ,, ?, !, ;, ( and ) are separators. A sentence consists of several words and separators.

Each maximal substring that does not contain separators is a word. That is, if a substring $S$ of a sentence contains no separators, and there does not exist another substring $T$ of the sentence such that $T$ contains no separators, $S$ is a substring of $T$, and $S \ne T$, then $S$ is a word in that sentence.

Additionally, the sentences in the input have the following properties:

• A sentence will not contain two words from different languages at the same time.
• A sentence contains at least one word from some language.
• A sentence may contain words that do not appear in any language’s known word list.

A sentence belongs to a language if and only if there exists a word $S$ in the sentence that comes from that language.

Input Format

The first line contains an integer $N$, the number of different languages.

Then follow $N$ lines. Each line contains the name of a language and several known words from that language, separated by spaces.

Then there is a blank line.

Then several lines (no more than $10^3$ lines), one sentence per line.

Output Format

For each sentence, output a single line with the name of the language it belongs to.

4
Qzrian yy ghy qzr
Yugoslavian mihailova petrozavodsk saint-petersburg
Suissvia yugoslavia korse mais kohnin
Mohaian Jzm Wallace Zhangbaohua djh 

yy,qzr and ghy are i don't know
mihailova saZk amOmlio
mais c'est pas Ca
wallace is good

Qzrian
Yugoslavian
Suissvia
Mohaian

Hint

For $100\%$ of the testdata, $1 \le N \le 100$, and each input line does not exceed 256 characters.

Translated by ChatGPT 5