Problem Description

Recently, intelligence agents have obtained some encrypted articles, where each word is very long. The codebreakers have come up with a method to simplify the words: they want to take the shortest possible prefixes for each word, but the chosen prefixes must not be prefixes of any other word.

This task has now been assigned to you.

Explanation: "String $\text{S}_1$ is a prefix of $\text{S}_2$" means that if you remove some characters from the end of string $\text{S}_2$ to match the length of $\text{S}_1$, $\text{S}_2$ becomes identical to $\text{S}_1$. For example: $\texttt{abc}$ is a prefix of $\texttt{abcaade}$ and $\texttt{abc}$, but not of $\texttt{abadc}$.

Input Format

The first line contains an integer $N$, representing the number of words.

Below are $N$ lines, each containing a word.

Output Format

There will be $N$ lines, each containing a word, corresponding to the simplified versions of the $N$ words above.

Sample Input and Output

Sample Input #1

3   
abc 
efg 
ijh

Sample Output #1

a
e
i

Sample Input #2

3
aac
aad
aae

Sample Output #2

aac
aad
aae

Notes

For $100\%$ of the data, $1 \le N \le 50$, and the length of each word does not exceed $50$, consisting only of lowercase letters.

It is guaranteed that no word is a prefix of another word.

见题面 Input 部分

见题面 Output 部分