Problem E
Joe is learning to speak
Joe is a 4-year-old child learning to speak his mother tongue. He tried to memorize every possible sentence in the language but he soon realized that the number of different sentences is unbounded. He decided to concentrate on memorizing the subsequences of size up to $n$ and their meaning. Joe understands a sentence if he has previously memorized all its subsequences of size $\leq n$.
Every afternoon, Joe starts reading sentences one by one. He remembers everything he has learned in the previous days. After reading a sentence, he asks for every word he doesn’t know and learns it. If he can’t fully understand the sentence he asks for the meaning of the whole sequence. After this, he memorizes every subsequence of size up to $n$ and reads the next sentence.
For example: supose that Joe memorizes only subsequences of 1 or 2 words and he already knows the sentences “I live in a house” and “This is a green house”. He will fully understand the sentence “I live in a green house”, since he already knows all the subsequences of size 1 and 2. However, if he decided to memorize subsequences up to size 3, he will ask for the meaning of the whole sentence because “in a green” is not a subsequence of size 3 in any previous sentence.
Obviously, Joe always knows his name.
Input
Input consists of several cases, each case begins with a line indicating the maximum size $n$ ($2 \leq n \leq 5$) that Joe can memorize.
The next lines contain the sentences with the previous knowledge Joe memorized in the previous days. The character * indicates the end of the previous knowledge. Below the *, there is a text containing several sentences that Joe is going to learn today. The symbol # indicates the end of the sentences that Joe is going to read today.
Both sections have up to 20000 different words. The sentences are terminated with any of the following characters that will appear as a separate token in the input: . , : ; ? !
Each word has size at most 20. The maximum number of words per sentence is 100. The maximum number of sentences per section is 1000. Sentences may appear more than once.
All the words contain only roman letters, no numbers or other symbols are used except the sentence separators. Words that differ only on the case of the letters are considered the same. For example: Joe, JOE and joE represent the same word.
There is at least one space or newline between each token. You should ignore other whitespace.
Output
For each test case, a line with the text Learning case C where $C$ is the number of the case starting by 1. Outputs for different test cases should be separated by a blank line.
For every unknown word $W$ he asks for the meaning with the following question: What does the word "W" mean? For every sentence $S$ not understood by Joe, he asks What does the sentence "S" mean? Output both $W$ and $S$ the same case as they appear. The words in $S$ must be separated with exactly 1 space.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 hello sam . say hello to everybody . good bye . * say hi to everybody . hi to everybody . hello joe . swerc # 4 Joe is my name . I have a dog . My dog is a cinnamon coloured golden retriever . The name of my father is Ben and the name of my mother is Linda . * Hello Joe , how are you ? Are you my friend ? Last day you told me : the name of my mother is Linda . You also told me : the name of my father is Ben . How are you my friend ? # |
Learning case 1 What does the word "hi" mean? What does the sentence "say hi to everybody" mean? What does the sentence "hello joe" mean? What does the word "swerc" mean? Learning case 2 What does the word "Hello" mean? What does the sentence "Hello Joe" mean? What does the word "how" mean? What does the word "are" mean? What does the word "you" mean? What does the sentence "how are you" mean? What does the word "friend" mean? What does the sentence "Are you my friend" mean? What does the word "Last" mean? What does the word "day" mean? What does the word "told" mean? What does the word "me" mean? What does the sentence "Last day you told me" mean? What does the word "also" mean? What does the sentence "You also told me" mean? What does the sentence "How are you my friend" mean? |
