Longest Concatenated Word

You are given a list of words. Your task is to find the longest word in the list that can be constructed by concatenating copies of shorter words also present in the list. A word is considered concatenated if it is formed by joining two or more words from the list. If there is no such word, output an empty string.

Note: A word cannot use itself in its own formation. The answer that is longer in length should be returned. In case of a tie in lengths, return the lexicographically smallest one.

Examples:

Input: 5
cat
 dog
 catdog
 cats
 dogcatsdog
Output: dogcatsdog
Input: 4
abcd
abc
def
abcddef
Output: abcddef

</p>

inputFormat

The first line contains an integer n, the number of words. Each of the next n lines contains a single word.

outputFormat

Output a single line containing the longest concatenated word. If no such word exists, output an empty string.

## sample

5
cat
dog
catdog
cats
dogcatsdog

dogcatsdog