Longest Beautiful String

You are given a word list stored in a file words.txt, where each line contains a word consisting only of lowercase English letters.

A string \( s = c_1c_2\cdots c_n \) of length \( n \) is called a beautiful string if and only if:

• Either \( n=1 \);
• Or \( n>1 \) and there exists a beautiful string \( s' \) of length \( n-1 \) such that, after reordering the characters of \( s' \), they are identical to the multiset of characters in the prefix \( c_1c_2\cdots c_{n-1} \) of \( s \). In other words, if we let \( sorted(x) \) denote the sorted order (in increasing order) of the characters of string \( x \), then we require that there exists a beautiful string \( s' \) (of length \( n-1 \)) with: \[ sorted(s') = sorted(c_1c_2\cdots c_{n-1}). \]

Your task is to find the longest beautiful string from the given word list. If there are multiple answers having the maximum length, output the lexicographically smallest one.

Example:

• Suppose the file words.txt contains: b, bc, cbd, dbca.
• s_1 = b is beautiful because its length is 1.
• s_2 = bc is beautiful because its prefix b (after sorting remains b) is a beautiful string.
• s_3 = cbd is beautiful because its prefix cb sorted equals bc, and bc is beautiful.
• s_4 = dbca is beautiful because its prefix dbc sorted equals bcd, and cbd is beautiful since sorted(cbd)=bcd.
• The answer is dbca (the longest beautiful string).

inputFormat

The input begins with an integer \( T \) denoting the number of words. The following \( T \) lines each contain a word consisting of lowercase English letters. This represents the contents of words.txt.

outputFormat

Output a single line containing the longest beautiful string. If there are several answers, output the lexicographically smallest one.

sample

4
b
bc
cbd
dbca

dbca