Pochi sanno che mucche amano giochi di parole: cruciverba, griglie di ricerca e molti altri.

Per progettarli serve aiuto informatico. Ci sono $N$ parole distinte ($2 \le N \le 20{,}000$), ognuna fino a 100 caratteri, solo minuscole a..z.

Trova due parole col prefisso comune più lungo: primi $C$ caratteri uguali, $C$ massimo fra tutte le coppie. Almeno una coppia con prefisso comune è garantita.

Se più di due coppie hanno lo stesso massimo, scegli quella con la prima parola più vicina all'inizio dell'elenco dato, poi con l'altra parola di prefisso massimo anch'essa più vicina all'inizio.

Input

• Riga $1$: intero $N$.

• Righe $2..N+1$: una parola ciascuna.

Output

Due righe, una parola ciascuna.

Esempi

Input 1

9
noon
is
lunch
for
most
noone
waits
until
two

Output 1

noon
noone

Crediti: Dan Adkins, 2001.