You are given n distinct contact names with the guarantee that no name is a prefix of another. For every name, output its shortest unique prefix: the shortest prefix such that no other name in the list has that same prefix.

Because a prefix of a given length is a single fixed string, the shortest unique prefix of each name is unique. Names consist of lowercase English letters only.

Input format

Line 1: an integer n. Line 2: n space-separated distinct names (no name is a prefix of another).

Output format

Print n lines; line i is the shortest unique prefix of the i-th name, in input order.

Constraints

• 1 <= n <= 100000
• Each name has length 1..30, lowercase letters.
• The names are distinct and prefix-free (no name is a prefix of another).

3
dog cat cow

d
ca
co

2
a b

a
b