Längste erreichbare Zeichenkette
Sie haben eine Menge von Zeichenketten. Ihre Aufgabe besteht darin, die längste Zeichenkette zu ermitteln, die sich konstruieren lässt, indem Sie Zeichen von links an eine leere Zeichenkette anhängen, wobei jede Zwischenschritt-Zeichenkette in der ursprünglichen Menge enthalten sein muss. Gibt es mehrere Zeichenketten mit derselben maximalen Länge, so geben Sie die Zeichenkette aus, die in lexikografischer Reihenfolge am kleinsten ist.
Eingabe
In der ersten Zeile steht eine ganze Zahl
n (1 ≤ n ≤ 100 000), die die Anzahl der Zeichenketten in der ursprünglichen Menge angibt.
In den folgenden n Zeilen finden sich diese Zeichenketten. Jede Zeichenkette besteht aus Kleinbuchstaben des englischen Alphabets und hat eine Länge zwischen 1 und 30.Ausgabe
Geben Sie die längste Zeichenkette aus, die unter den genannten Bedingungen konstruiert werden kann. Falls keine solche Lösung existiert, geben Sie eine leere Zeichenkette aus.
Beispiele
Eingabe | Ausgabe |
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