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.
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 .
For each string s in the input, output a single line containing the successor string t.
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”