Concatenated Words

easy

1. You are given an array of strings containing words (without duplicates).
 2. You have to return all concatenated words in the given list of words.
 3. A concatenated word is defined as a string that is made of at least two shorter words in the given array.
 4. For example:
 Input: ["pep","coding","pepcodingpep","pepcoding","codingpepcoding","peace","excellence","peaceexcellencecoding"]
 
 Output: [codingpepcoding,peaceexcellencecoding,pepcoding,pepcodingpep]
 
 Note:
 1. The order of returned elements does not matter.
 2. main takes input from the users.
 3. This is a functional problem. 
 4. You have to complete the function find. It takes as input an array of strings containing words. It should return the required arraylist.
 5. Don't change the code of main, display and other utility functions.

Input Format

First line takes input N, the length of the array. Second line takes input N space separated strings, representing the elements of the array. Input is handled for you.

Output Format

All the concatenated words in sorted order. Output is handled for you.

Constraints

The number of elements of the given array will not exceed 10,000.
 The length sum of elements in the given array will not exceed 600,000.
 All the input string will only include lower case letters.

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 
pep coding pepcodingpep pepcoding codingpepcoding peace excellence peaceexcellencecoding

Output

codingpepcoding peaceexcellencecoding pepcoding pepcodingpep

Implement Trie