CF858D.Polycarp's phone book

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.

Polycarp 的手机通讯录中有 $n$ 个电话号码。每个号码是一个 9 位整数，且首位数字不为 0。所有号码互不相同。

Polycarp 的手机上安装了最新版本的 Berdroid 操作系统。当用户输入一串数字时，系统会显示通讯录中所有包含该数字串作为子串的电话号码。例如，若 Polycarp 的通讯录中有三个电话号码：123456789、100000000 和 100123456，则：

• 若他输入 00，将显示两个号码：100000000 和 100123456；
• 若他输入 123，将显示两个号码：123456789 和 100123456；
• 若他输入 01，将只显示一个号码：100123456。

对 Polycarp 通讯录中的每个电话号码，请找出长度最短的一串数字，使得当 Polycarp 输入该串时，Berdroid 系统仅显示该电话号码（即该数字串是该号码的子串，但不是其他任何号码的子串）。

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.

第一行包含一个整数 $n$（$1 \leq n \leq 70000$）—— 表示 Polycarp 通讯录中电话联系人的总数。

随后是 $n$ 个电话号码，每行一个。每个号码是一个 9 位正整数，且首位数字为 $1$ 至 $9$ 中的一个。所有号码互不相同。

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.

恰好输出 n 行：其中第 i 行应包含最短的非空数字序列，使得 Polycarp 输入该序列后，Berdroid 操作系统仅显示联系人列表中的第 i 个号码。若存在多个满足条件的序列，则输出其中任意一个即可。