Peu le savent, mais les vaches aiment les jeux de mots : leurs mots croisés, grilles de recherche et beaucoup d'autres jeux.

Elles ont besoin d'aide informatique pour les concevoir. Il y a $N$ mots distincts ($2 \le N \le 20{,}000$), chacun d'au plus 100 caractères, uniquement les minuscules a..z.

Trouvez les deux mots de plus long préfixe commun : leurs $C$ premiers caractères coïncident et $C$ est maximal parmi toutes les paires. Au moins une paire partage un préfixe.

Si plus de deux paires atteignent la même longueur maximale, choisissez celle dont le premier mot est le plus proche du début de la liste fournie, puis dont l'autre mot du préfixe maximal est aussi le plus proche du début.

Entrée

• Ligne $1$ : entier $N$.

• Lignes $2..N+1$ : un mot par ligne.

Sortie

Deux lignes, chacune un mot.

Exemples

Entrée 1

9
noon
is
lunch
for
most
noone
waits
until
two

Sortie 1

noon
noone

Source : Dan Adkins, 2001.