You are given a list of words. You need to find the shortest prefix of each word so that it can identify the word uniquely.

Examples:

Words: ["program", "code", "process", "coding", "type", "print"]
Output: ["prog", "code", "proc", "codi", "t", "pri"]

Note: Assume, no word is prefix of another. Hence, a unique prefix is always possible.

Testing

Input Format

The input contains the following lines:

• An integer ‘n’ denoting the number of words in the list.
• n space-separated words, denoting the list.

Output format

Space-separated strings, each denoting the shortest prefix identifying its respective word.

Sample Input

6
program code process coding type print

Expected Output

prog code proc codi t pri

Constraints

1 <= n <= 105
1 <= word length <= 10
Words have only lower-case characters (a-z).