Longest Reachable String
You are given a set of strings. Your task is to find the longest string that can be constructed by adding characters to the left, starting from an empty string, in a way that all the intermediate strings during this process belong to the initial set. If there are multiple strings that have the same maximum length, output the string that has the smallest lexicographical order.
Input
The first line contains an integer
n (1 ≤ n ≤ 100 000), representing the number of strings in the initial set.
The next n lines contain the strings from the initial set. Each string consists of lowercase English letters and has a length between 1 and 30.Output
Output the longest string that can be constructed using only the given set of strings. If no such string exists, output an empty string.
Examples
Input | Output |
7
pr
profound
f
found
fo
foun
fou | found |
3
ab
abc
abcd | ㅤ |
5
a
ab
aba
abaz
abad | abad |
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB