Trova il Successore
Vi viene fornito un elenco di
n stringhe. Per ognuna di queste stringhe s, dovete determinare una stringa successiva t presente nello stesso elenco (potendo anche coincidere con s).
La stringa successiva è definita come la stringa più piccola che compaia all’inizio di s.Input
La prima riga dell’input contiene un singolo intero,
n (1 ≤ n ≤ 100 000), che rappresenta il numero di stringhe nell’elenco.Le successive
n righe contengono le stringhe. Ciascuna stringa è formata da lettere minuscole dell’alfabeto inglese.È garantito che il numero totale di caratteri nell’input non sia superiore a .
Output
Per ogni stringa
s in ingresso, stampate in una nuova riga la relativa stringa successiva t.Esempi
Input | Output |
5
abaca
aba
abacaba
bacab
dabacaba | aba
aba
aba
bacab
dabacaba |
Spiegazione
Per la stringa “abaca” la stringa successiva è “aba”.
Per la stringa “aba”, la successiva è “aba” stessa.
Per la stringa “abacaba” la stringa successiva è “aba”.
Per la stringa “abcab” la stringa successiva è “bacab”.
Per la stringa “dabacaba” la stringa successiva è “dabacaba”.
Constraints
Time limit: 7 seconds
Memory limit: 512 MB
Output limit: 1 MB