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

To check your solution you need to sign in