Word Extension

Huihyeon likes a word game where one lowercase English letter is inserted into a word to make a new word. In one move, the letter may be inserted at the beginning, at the end, or anywhere in the middle. The newly made word must appear in the dictionary.

The dictionary contains d words, and each word consists only of lowercase English letters with length at most 80. Starting from the three-letter word first spoken by the teacher, find the longest word that can be made by repeatedly following this rule.

The first line contains the number d of dictionary words and the starting word. (1 ≤ d ≤ 1,000) The starting word has length 3 and is included in the dictionary.

Each of the next d lines contains one dictionary word.

Print one longest word that can be made while following the rule. If there are multiple possible answers, any one of them may be printed.

Starting from cal, one can add one letter at a time in the order coal, coral, choral, chorale to reach a longest word.