Concatenated Words Finder

Given a list of words, your task is to find all the concatenated words. A word is called a concatenated word if it is formed by concatenating at least two smaller words from the list. Formally, a word \(w\) is concatenated if it can be expressed as \(w = w_1 + w_2 + \cdots + w_k\) for some \(k \ge 2\), where each \(w_i\) is a word from the list.

inputFormat

The first line contains an integer \(n\) which represents the number of words. The following \(n\) lines each contain a single word consisting of lowercase letters.

outputFormat

Output all the concatenated words separated by a single space. If there are no concatenated words, output an empty line.

8
cat
cats
catsdogcats
dog
dogcatsdog
hippopotamuses
rat
ratcatsdog

catsdogcats dogcatsdog ratcatsdog