Trouver le successeur
On vous donne une liste de
n chaînes de caractères. Pour chaque chaîne s de la liste, votre tâche consiste à trouver la chaîne successeur t provenant de la même liste (y compris le cas où t est identique à s).
La chaîne successeur est la plus petite chaîne qui apparaît au début de la chaîne s.Entrée
La première ligne de l’entrée contient un entier
n (1 ≤ n ≤ 100 000), qui représente le nombre de chaînes dans la liste.Les
n lignes suivantes contiennent les chaînes de caractères. Chaque chaîne est composée de lettres minuscules anglaises.Il est garanti que le nombre total de caractères dans l’entrée ne dépasse pas .
Sortie
Pour chaque chaîne
s dans l’entrée, affichez une seule ligne comportant la chaîne successeur t.Exemples
Entrée | Sortie |
5
abaca
aba
abacaba
bacab
dabacaba | aba
aba
aba
bacab
dabacaba |
Explication
Pour la chaîne “abaca”, la chaîne successeur est “aba”.
Pour la chaîne “aba”, la chaîne successeur est “aba” elle-même.
Pour la chaîne “abacaba”, la chaîne successeur est “aba”.
Pour la chaîne “abcab”, la chaîne successeur est “bacab”.
Pour la chaîne “dabacaba”, la chaîne successeur est “dabacaba”.
Constraints
Time limit: 7 seconds
Memory limit: 512 MB
Output limit: 1 MB