Description

Some are playing a travel game while they are taking a travel.

In this game, the first one thinks of a three letter word from the Sacred Travel Game Dictionary (STGD). The next one in line must add a letter to the word (at the beginning, between two letters, or at the end) to make another word in the STGD. They are curious as to just how big the final word can be.

Given a dictionary of D (1 <= D <= 1000) words and a starting word, find any of the longest possible words that can be formed playing this travel game.

Input

Many cases. In each case,first line is a integer D followed by a space followed by a legal three letter word. And then D lines Each line contains a legal word no longer than 80 characters, consisting only of lowercase letters, from the STGD.

Output

A single line with the longest word that can be formed by extending the input seed for each case. The input ensure the correct result will be unique.

Sample

Input

9 cal
cal
calf
calfs
call
calls
choral
chorale
coal
coral

Output

chorale

Hint

[From the sequence: cal, coal, coral, choral, chorale]

Source: daimin