Find The Successor
You are given a list of
n strings. For each string s in the list, your task is to find the successor string t from the same list (including the case when t is equal to s).
The successor string is the smallest string that appears at the beginning of string s.Input
The first line of the input contains a single integer,
n (1 ≤ n ≤ 100 000), representing the number of strings in the list.The following
n lines contain the strings. Each string consists of lowercase English letters.It is guaranteed that the total number of characters in the input does not exceed .
Output
For each string
s in the input, output a single line containing the successor string t.Examples
Input | Output |
5
abaca
aba
abacaba
bacab
dabacaba | aba
aba
aba
bacab
dabacaba |
Explanation
For the strings “abaca” the successor string is “aba”.
For the string “aba” the successor string is “aba” itself.
For the strings “abacaba” the successor string is “aba”.
For the string “abcab” the successor string is “bacab”.
For the string “dabacaba” the successor string is “dabacaba”
Constraints
Time limit: 7 seconds
Memory limit: 512 MB
Output limit: 1 MB