Problem 115: Fullexicalinkage

(U.M. ACM Runoffs 2003, problem 2)

Description

The people of Germania like big words. They especially like words that are made by running together the individual words of a descriptive phrase (for example, the Germanian words for "cat" and "food" are FourLegTailFurBiteAnimal and MouthInHungerGoneSubstance). Most of all, they like run-together words in which the last letter of each component word in the sequence is the same as the first letter in the following word. When they manage to invent a word like that, they are really happy, and overlap the component words so that the repeated letter only appears once. For example, the Germanian word for "Librarian" is made from the words "Book Keeping Guy" all run together to make "Bookeepinguy". Notice that the word only contains one K and one G.

You must write a program that the Germanians can use to help them make up new words of their favourite kind. Your program will be given a list of words as input, and it must try to find some arrangement of those words in which the last letter of each word is the same as the first letter of the following word.

If such an arrangement exists, the resulting run-together word should be printed, with the overlap letters removed as explained above. Only the single final letter of each word is removed (so Fee Eels is reduced to Feeels, not Feels), and of course, the last letter of the last word is kept. If there is more than one possible arrangement, print the one that comes first in alphabetical ordering. If there is no possible arrangement, print out ---- (four dashes).

Input Format

The input consists of a sequence of word sets. Each word set begins with a line containing single integer (between 1 and 20 inclusive) indicating the number of words in the set. That number of words then follow. Each word is on a separate line. Words consist only of lower case letters. After the last word set there is a line containing the number 0.

Output Format

For each wordset, print the run-together word, all in lower case, one per line. If more than one word is possible, print the one that would come first in a dictionary. If there is no possible run-together word, print "----".

Limits

No word set will contain more than 20 words or fewer than 1 word. No word will be longer than 20 characters. Every word will consist of at least two characters. No word set will contain more than three words beginning with the same letter.

Sample Input

3
full
lexical
linkage
3
linkage
full
lexical
3
partial
lexical
connection
4
cxxxd
dyyyc
azzzd
dwwwa
0

Sample Output

fullexicalinkage
fullexicalinkage
----
azzzdyyycxxxdwwwa