Larry is playing a word game in English class. The game is a 2-player turn-based game: Larry and his English teacher. On the first turn, Larry goes first, and then he alternates turns with his teacher. On the first turn, Larry chooses a letter, then the next player has to add a letter to it. The current sequence of words has to be a prefix of a word in the teacher's size dictionary of words, and the first person to spell a complete word loses. If Larry beats his English teacher, he gets bonus marks, so Larry wants to win. Can you help Larry find who will win, and what word the loser will end up spelling?
Input Specification
The first line will contain the integer .
The next lines will a lowercase string .
Output Specification
On the first line, print hudab
or baf
if Larry wins or loses. On the next line, print the word that the loser will spell out, given both players play optimally. If there are multiple such words, print the lexicographically least.
Subtasks
Subtask 1 [30%]
Subtask [70%]
No further constraints.
Sample Input
4
baf
baffled
larry
larrycreep
Sample Output
baf
baf
Explanation for Sample Input
Larry can win if his teacher spells larrycreep
, however, his teacher cannot spell that unless Larry spells larry
(causing Larry to lose). The other 2 words are baf
and baffled
which both lose for Larry, so Larry cannot win the game. The lexicographically least losing word is baf
.
Comments