Concatenated Words

hard

Given an array of strings words, return all the concatenated words in the given list of words.
Concatenated word is a word that can be created by concatination of at least two other shorter words from the list.

You can return concatination words in any order

Input Format

n count of words in list word1 word2 ... n words

Output Format

Output is managed for you

Constraints

1. 1 &lt;= words.length &lt;= 10^4
2. 1 &lt;= words[i].length &lt;= 1000
3. words[i] consists of only lowercase English letters.
4. all word's in the list are unique.
5. 0 &lt;= sum(words[i].length) &lt;= 10^5

Notice

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

Example

Input

8
cat
cats
catsdogcats
dog
dogcatsdog
hippopotamuses
rat
ratcatdogcat

Output

catsdogcats
dogcatsdog
ratcatdogcat

Convert Bst To Sorted Doubly Linked List

Punish The Students