Chaîne la plus longue atteignable

On vous fournit un ensemble de chaînes de caractères. Votre objectif est de repérer la chaîne la plus longue que l’on peut construire en ajoutant des caractères sur la gauche, en partant initialement d’une chaîne vide, tout en veillant à ce que chacune des chaînes intermédiaires apparaisse dans l’ensemble de départ. S’il existe plusieurs chaînes de longueur maximale, il faut retourner celle dont l’ordre lexicographique est le plus petit.

Entrée

La première ligne contient un entier n (1 ≤ n ≤ 100 000), qui représente le nombre de chaînes incluses dans l’ensemble initial.
Les n lignes suivantes comportent chacune l’une des chaînes de l’ensemble. Chaque chaîne est formée de lettres minuscules de l’alphabet anglais et a une longueur comprise entre 1 et 30.

Sortie

Affichez la chaîne la plus longue qui peut être construite à partir de l’ensemble donné. Si aucune chaîne ne satisfait les conditions, affichez une chaîne vide.

Exemples