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).