Description

If the last letter of word $X$ is the same as the first letter of word $Y$, then $X$ and $Y$ can be concatenated as $X.Y$. Note: there is an English period . between $X$ and $Y$. For example, for the words dog and gopher, dog and gopher can be concatenated as dog.gopher.

More examples:

• dog.gopher
• gopher.rat
• rat.tiger
• aloha.aloha
• arachnid.dog

A concatenated word can be connected with other words to form a longer word chain, for example:

aloha.arachnid.dog.gopher.rat.tiger

Note that the letters on both sides of . must be the same.

Now you are given some words. Please find the lexicographically smallest word chain such that each word appears in the chain exactly once. Note that if the same word appears $k$ times, you must output it $k$ times.

Input Format

The first line contains a positive integer $n$ ($1 \le n \le 1000$), representing the number of words.

The next $n$ lines each contain a word consisting of $1$ to $20$ lowercase letters.

Output Format

Output a single line: the lexicographically smallest word chain that uses every given word exactly once. If such a chain does not exist, output exactly three asterisks ***.

6
aloha
arachnid
dog
gopher
rat
tiger

aloha.arachnid.dog.gopher.rat.tiger

Hint

• For $40\%$ of the testdata, $n \le 10$.
• For $100\%$ of the testdata, $n \le 1000$.

Translated by ChatGPT 5