View as PDF

Submit solution

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 32M

Problem type

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 N 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 N\ (3 \le N \le 10^5).

The next N lines will a lowercase string S\ (1 \le |S| \le 10^2).

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.


Subtask 1 [30%]

(1 \le N \le 100)

Subtask [70%]

No further constraints.

Sample Input


Sample Output


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.


There are no comments at the moment.