题目描述

奶牛们正在前往明尼苏达州的湖泊旅行。和其他人一样，它们感到无聊，于是玩起了“旅行游戏”来打发时间。

在这个旅行游戏中，第一头奶牛从神圣旅行游戏词典（STGD）中想出一个三个字母的单词。队伍中的下一头奶牛必须在这个单词的开头、两个字母之间或者结尾添加一个字母，从而形成神圣旅行游戏词典中的另一个单词。奶牛们想知道最终能形成的单词最大长度是多少。

给定一个包含$D$（$1$ <= $D$ <= $1000$）个单词的词典和一个起始单词，找出在这个旅行游戏中能够形成的任意一个最长的单词。

输入

• 第 1 行：整数$D$，后面跟一个空格，再跟一个合法的三个字母的单词。
• 第 2 行到第$D + 1$行：每行包含一个来自神圣旅行游戏词典的合法单词，长度不超过 80 个字符，仅由小写字母组成。

输出

一行，包含通过扩展输入的起始单词能够形成的最长单词。

输入数据保证正确结果是唯一的。

示例输入

9 cal
cal
calf
calfs
call
calls
choral
chorale
coal
coral

示例输出

chorale

提示

[形成的单词序列为：cal, coal, coral, choral, chorale]

来源

USACO 2003 年 2 月 Orange 组