Do you remember Jan from the last year’s IPSC? He loves to play games with numbers. Now he is one year older and so he expanded his interests also to word games. Moreover he also involved his younger brother Maroš to play his new two player game. Poor small Maroš, he will never beat his older brother Jan without your help.
In the beginning, the players agree on a wordlist they’ll use for the game. The words in the wordlist must consist of lowercase English letters only.
The game starts with an empty string S. Players take alternating turns, starting with Maroš. In each turn, the current player must append a letter to the end of S.
The player that either creates a string from the wordlist, or creates a string S that is not a prefix of any word in the wordlist, loses the game.
Your task is to play this game against our server, and win it.
The input file contains the wordlist that will be used. Its first line contains one integer N – the number of words in the wordlist. N lines follow, each of them contains one of the words. No two words in the wordlist are equal, and all the words contain lowercase English letters only.
Submit a text file with the description of the move you want to make.
If you want to continue playing the current game, the file shall contain a single line with a single lowercase letter – the letter you want to append to the current string.
If you want to give up the current game and start a new one, the file shall contain a single line of the form “RESTART x”, where x is the lowercase letter you want to play in your first move.
If your submission does not represent a valid move, you will get a corresponding error message, and the state of the game will not be altered.
If your submission causes you to lose the game, you will get a corresponding error message, and the game is restarted.
If your submission causes you to win the game, it will be accepted, and you will receive points for solving the corresponding input.
In the remaining case (a valid move that does not terminate the game), you will get a message describing our move.
Note that for each data set there is a strict limit: you can only make a total of ten submissions. Play carefully – if you give up a game after 8 moves, chances are you will not have enough submissions left to win the second one.
Also, you may assume that our player knows the optimal strategy, and that it is really nasty :-)