Longest Concatenated Word

Given a list of words, find the longest word that can be constructed by concatenating other words from the list. Each word can be used more than once. If there is a tie, you may output any one of them. If no such word exists, output an empty string.

Note: The concatenated word must be formed by at least two smaller words from the list.

Example:

Input:
5
cat
dog
mouse
catdog
housecat
Output:
catdog

</p>

inputFormat

The first line of input contains an integer N representing the number of words. Each of the following N lines contains a single word.

outputFormat

Output the longest word that can be formed by concatenating other words from the provided list. If no such word exists, output an empty string.

## sample

5
cat
dog
mouse
catdog
housecat

catdog