鮮為人知,牛喜歡文字遊戲。有牛填字、找詞網格及各種其他文字遊戲。
設計某些遊戲需要電腦幫忙。有 $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。