P3752 Language Census

“Kiaosmaonsnai Assi fi wais.” “Kjamqosoaksi mais pas?” “Oci! Asia olo mnai naso!” “2333 what are they even saying, I can’t understand at all...” This is everyday life in Yugo. The people of Yugo are conducting a population census. Since Yugo is a typical multi-ethnic country, it has many languages.

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.

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.

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

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