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

To check your solution you need to sign in
Sign in to continue