GHOST

GHOST is a spelling game played by bored school kids on long car/bus rides. The purpose of the game it to accumulate letters that spell some word without ever actually finishing a word. Before the game begins, players agree on the order in which they will play. Plays proceed from one player to the next, returning then to the first player until the game is completed. Each player must, in turn, 1) extend the current “word”, 2) bluff, or 3) challenge.

1. The most common play is to extend the current sequence of letters by adding a single letter, so that the resulting sequence of letters forms the beginning of some word. For example, the first player might call “P”, thinking (secretly) of the word “part”. The second player might call “L”, thinking of the word “play”. The third player might call “E”, thinking of the word “please”.
   A player loses if they actually complete a valid English word of 4 or more letters. For example, if there were only three players, after “PLE” the first player might try to extend the word by calling “A”, thinking of the word “plead”. This would, however, be a losing play because “plea” is a valid word.
2. A player who cannot think of a valid letter to extend the current sequence may opt to “bluff” by calling out an arbitrary letter, hoping that the next player will not notice.
3. Finally, if a player believes, on his turn, that the preceding player was bluffing or that the preceding player completed a word, he may challenge the preceding player. If all players agree that the current sequence completes a word (of at least 4 letters), the preceding player loses. If the preceding player cannot name a word that can be formed from the current sequence, the preceding player loses. If the current sequence is not a valid word and the preceding player is able to name a possible word beginning with the sequence, the challenger loses.

Write a program to serve as a player in a game of GHOST. Note that a skillful player will, on her turn, not only worry about coming up with a legal extension to the current sequence of letters, but will also think about all the words that could be formed from an extension and whether, comparing the number of letters in those words to the number of players, consider whether a possible extension could result in her getting stuck on a future turn with no legal extension that does not end a word, thus losing the game.

The input for this game will consist of a sequence of one or more scenarios.

Each scenario contains the following:

The first line of the scenario will contain a single integer indicating the number of players in the
game. This value will be at least 2 for a valid scenario. The end of the input file will be indicated by a value less than 2 for this number.

Following this will be a list of words to serve as the program’s dictionary/vocabulary for the scenario. Each word will appear on a separate line, with no leading, trailing, or internal whitespace. Each word will consist only of the characters {a–z}. The end of this list of words will be signaled by an empty line.

Following that empty line, the final input line of the scenario will contain the current sequence of letters, again with no leading or trailing spaces. This sequence may be empty if the computer player is the first player. The sequence may also contain more letters than the number of players, indicating that all players (including the computer player) have taken one or more turns.

Your program will produce a single line of output for each scenario.

That line of output will consist of the current sequence of letters from the input, followed by a single blank, followed by:

1. The word “Challenge” if the current sequence is a complete word in the vocabulary list or is not a prefix of any word in the vocabulary list, or
2. A single character representing a valid extension if it can find some word formed with that extension such that this extension does not complete a word and, if all other players continue to spell out that same word, neither that word nor any shorter word would be completed on the computer player’s turn.
   If multiple such extensions are possible, and if any extensions guarantee a different player will lose, the program should select one of those.
3. The word “Bluff” if the only possible extensions would lead to a loss by the computer player.