Мало кто знает, что коровы любят словесные игры: свои кроссворды, сетки поиска слов и многие другие.

Для разработки нужна помощь компьютера. Есть $N$ различных слов ($2 \le N \le 20{,}000$), каждое не длиннее 100 символов, только строчные a..z.

Найдите два слова с самым длинным общим префиксом: первые $C$ символов совпадают, а $C$ максимально среди всех пар. Хотя бы одна пара с общим префиксом гарантирована.

Если более двух пар имеют одинаковую максимальную длину, выберите пару с первым словом ближе всего к началу исходного списка, затем с другим словом максимального префикса также ближе всего к началу.

Входные данные

• Строка $1$: целое $N$.

• Строки $2..N+1$: по одному слову.

Выходные данные

Две строки, по одному слову.

Примеры

Входные данные 1

9
noon
is
lunch
for
most
noone
waits
until
two

Выходные данные 1

noon
noone

Источник: Dan Adkins, 2001.