Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3345

Time Limit: 1 Second      Memory Limit: 32768 KB

Xii is a very talented student who is interested in languages. By now she has learnt more than 10 computer languages and can use them to write powerful programs. But recently she was considering learning more human languages, so she picked Chinese, English, Japanese and German to learn.

Learning four foreign languages at the same time seemed unbelievable, but it was quite easy for our language genius Xii. It took only a few days for her to learn some basic sentence patterns and some frequently used words.

Following is the sentence patterns Xii has learnt.

  1. Chinese: [pn] shi [n]
  2. Chinese: [pn] [vi]
  3. Chinese: [pn] [vt] [n]
  4. Chinese: ni hao
  5. English: [pn] [vi]
  6. English: [pn] [vt] [n]
  7. English: There is a [n]
  8. English: Happy new year
  9. Japanese: [pn] ha [n] desu
  10. Japanese: [pn] ha [n] da
  11. Japanese: [pn] ha [n] ga [adj] desu
  12. Japanese: [n] saikou
  13. Japanese: yoi otoshiwo
  14. German: Ich habe ein [n]
  15. German: Ich bin [n]
  16. German: Ich heisse [n]
  17. German: Du hast [n]
where those with brackets represent catalogs and others are fixed word. Words arranged in one of the forms above form a correct sentence. But if a sentence contains one or more words that don't belong to a certain language, this sentence of cource doesn't belong to this language. For example, "watashi" belongs to "[pn]" catalog in Japanese and "tensai" belongs to "[n]" catalog in Japanese. Then the sentence "watashi ha tensai da" is Japanese. But if "Ich" is not a "[pn]" in Japanese, then "Ich ha tensai da" is not Japanese.

Xii was happy to learn so many languages and she tried to write down some lines, although she might wrote wrong sentences or wrong words. Now you are given the vocabulary of Xii and some sentences she wrote down, you are to tell which languages they belong to.


First line is the number of test cases T (1 <= T <= 5).

Following are T cases. For each case, the first line is the number of words n and the number of sentences Xii wrote m (1 <= n <= 20, 1 <= m <= 20). The next n lines describe the n words. Each line is three parts separated by spaces. The first part is the language it belongs to, and it is one of the four languages above. The second part is the catalog, and it belongs to what appear in the sentence patterns. The third part is the word which composed of no less than 1 and no more than 10 English letters. Note that a word may belong to different languages or belong to different catalogs of same language. Following m lines are what she wrote down. A sentence will not be more than 20 words and will not be longer than 30.


For each case, first print a line "Case #?:" where ? is the case number starting from 1.

Then print what language each sentence belongs to. If the sentence does not fit to any sentence patterns, print a line "I don't know.". A sentence will belong to at most one sentence pattern.

Sample Input

10 4
German [n] Apfel
Japanese [adj] suki
Chinese [n] ren
English [vt] drink
Chinese [pn] wo
English [n] milk
Japanese [pn] watashi
Japanese [pn] anta
Japanese [n] tensai
English [pn] They
watashi ha tensai da
Ich bin tensai
They drink milk
wo shi ran
1 1
German [n] Apfel
Ich habe ein Apfel

Sample Output

Case #1:
I don't know.
I don't know.
Case #2:

Author: ZHUANG, Junyuan
Contest: ZOJ Monthly, June 2010
Submit    Status