Unique Prefix Minimization

You are given a list of encrypted words. Since each word is very long, the decryption team decided to simplify them by replacing each word by its shortest possible prefix, with the constraint that the chosen prefix must not be a prefix of any other word in the list.

Formally, for two strings $S_1$ and $S_2$, we say that $S_1$ is a prefix of $S_2$ if by removing some (possibly zero) characters from the end of $S_2$, the string becomes exactly $S_1$. For example, abc is a prefix of both abcaade and abc, but not of abadc.

Your task is to find, for each word, the shortest prefix such that it is not a prefix of any other word.

inputFormat

The first line contains an integer n ($1 \le n \le 10^5$), representing the number of words. Each of the following n lines contains one word consisting only of lowercase letters. It is guaranteed that no word is the prefix of any other word.

outputFormat

Output n lines. The i-th line should contain the shortest prefix of the i-th input word such that this prefix is not a prefix of any of the other words.

sample

3
hello
helium
hero

hell
heli
her