Goku has returned back home after his training from King Kai's planet.

His wife Chi-Chi is very angry with him for leaving her alone for such a long time, once again! As soon as he enters his home, she starts screaming at him.



Goku's mind is still engrossed in finding and solving problems. He is not listening to his wife. Instead, he has devised a new problem for himself.

King Kai, during his training taught him about a data structure, called the Suffix Array. He taught him how to calculate the Longest Common Prefix (LCP) of any two strings from a given set of strings using the suffix array. He is trying to test his knowledge by using the words screamed out by Chi-Chi as the set of the strings, and finding the string which she has already screamed and which has the longest common prefix with the string that she is currently screaming. You need to provide him with the correct answers so that he can verify the results of his understanding of the new data structure he got to know about from King Kai.

You will be given an array containing n strings. For each string, you need to tell the index of the string which comes before that string in the array and has the longest common prefix with the current string. If there is no such string, print "-1" (without quotes). If there are multiple such strings, print the index of the string which occurs earliest.

Input :

First line contains an integer n, denoting the number of strings Chi-Chi screams.
The next n lines each contain the string.

Output :

For each string, print an integer in the new line, as described above.

Constraints :

1 ≤ t ≤ 100000
1 ≤ |s| ≤ 100000
Sum of lengths of all the strings ≤ 1000000