Longest Composite Word

Given a list of words, find the longest word that can be constructed by concatenating other words from the list. A word is considered composite if it is formed by joining two or more other words from the list. If there are multiple composite words with the same maximum length, return the one that appears first in the input order. If no such composite word exists, output an empty string.

Note: A word cannot be used to form itself. Each word from the input list may be used multiple times to form another word.

Formal Description:

Let \( W = \{w_1, w_2, \dots, w_n\} \) be the set of input words. Find a word \( w_k \in W \) with maximum length such that there exists a sequence of indices \( i_1, i_2, \dots, i_m \) (with \( m \ge 2 \)) satisfying \[ w_k = w_{i_1} \oplus w_{i_2} \oplus \cdots \oplus w_{i_m}, \] where \( \oplus \) denotes string concatenation and for all \( j \), \( w_{i_j} \in W \) and \( w_{i_j} \neq w_k \). If multiple answers exist, choose the one that appears earliest in the input list.

inputFormat

The input is read from standard input and is in the following format:

N
word1 word2 ... wordN

Where:

• N is an integer representing the number of words.
• The next line contains N words separated by spaces.

outputFormat

Output the longest composite word as described. If no composite word exists, output an empty string.

## sample

7
cat banana dog nana walk walker dogwalker

dogwalker