Polycarp's phone book

题意翻译

有 $n$ 个长度为 $9$ 且只包含数字字符且 **互不相同** 的串。 需要对于每个串找到一个 **长度最短** 的识别码，使得这个识别码 **当且仅当** 为这个串的子串。

题目描述

There are $ n $ phone numbers in Polycarp's contacts on his phone. Each number is a 9-digit integer, starting with a digit different from $ 0 $ . All the numbers are distinct. There is the latest version of Berdroid OS installed on Polycarp's phone. If some number is entered, is shows up all the numbers in the contacts for which there is a substring equal to the entered sequence of digits. For example, is there are three phone numbers in Polycarp's contacts: $ 123456789 $ , $ 100000000 $ and $ 100123456 $ , then: - if he enters $ 00 $ two numbers will show up: $ 100000000 $ and $ 100123456 $ , - if he enters $ 123 $ two numbers will show up $ 123456789 $ and $ 100123456 $ , - if he enters $ 01 $ there will be only one number $ 100123456 $ . For each of the phone numbers in Polycarp's contacts, find the minimum in length sequence of digits such that if Polycarp enters this sequence, Berdroid shows this only phone number.

输入输出格式

输入格式

The first line contains single integer $ n $ ( $ 1<=n<=70000 $ ) — the total number of phone contacts in Polycarp's contacts. The phone numbers follow, one in each line. Each number is a positive 9-digit integer starting with a digit from $ 1 $ to $ 9 $ . All the numbers are distinct.

输出格式

Print exactly $ n $ lines: the $ i $ -th of them should contain the shortest non-empty sequence of digits, such that if Polycarp enters it, the Berdroid OS shows up only the $ i $ -th number from the contacts. If there are several such sequences, print any of them.

输入输出样例

输入样例 #1

3
123456789
100000000
100123456

输出样例 #1

9
000
01

输入样例 #2

4
123456789
193456789
134567819
934567891

输出样例 #2

2
193
81
91