Problem C
Alphabet Animals
Given the last animal name said before your turn and a list of all names not yet used, can you make it through this turn? If so, can you make sure to eliminate the next player?
Input
The first line of input contains a single word, the animal that the previous player just said. The next line contains a single integer $n$ ($0 \le n \leq 10^5$), the number of valid unused animal names. Each of the following $n$ lines contains one valid unused animal name.
All animal names (including the one the previous player said) are unique and consist of at least $1$ and at most $20$ lower case letters ‘a’-‘z’.
Output
If there is any animal name you can play that eliminates the next player, output the first such name from the input list, followed by an exclamation mark. Otherwise, if there is any animal name that you can play, output the first such name. Otherwise, output a question mark (in this case you will just have to make up a fake name in the hope that the others will trust you that this is a real animal).
| Sample Input 1 | Sample Output 1 |
|---|---|
pig 2 goat toad |
goat |
| Sample Input 2 | Sample Output 2 |
|---|---|
dog 2 snake emu |
? |
| Sample Input 3 | Sample Output 3 |
|---|---|
hare 3 bee cat eagle |
eagle! |
