Longest Compound Word

Given a list of words, your task is to find the longest compound word in the list. A compound word is defined as a word that is composed entirely of at least two shorter words from the same list. Formally, a word \(W\) is compound if there exists an index \(i\) (\(1 \leq i < |W|\)) such that the prefix \(W[0:i]\) is a word in the list and the suffix \(W[i:]\) is either a word in the list or a compound word (i.e. it can be further decomposed into two or more words from the list).

If there is a tie among the longest compound words, you may output any one of them. If there is no compound word in the list, output an empty string.

inputFormat

The first line contains a single integer \(n\) (the number of words). Each of the next \(n\) lines contains one word. All words consist of lowercase English letters.

outputFormat

Output a single line containing the longest compound word. If there is no compound word, output an empty string.

6
cat
dog
walker
dogwalker
catdog
catwalker

dogwalker