鲜为人知,牛喜欢文字游戏。它们有牛填字、找词网格及各种其他牛文字游戏。
设计某些游戏需要电脑帮助。有 $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。