← 返回题目列表

Codeforces · 858/D

D. 波利卡普的电话簿

中文机器翻译题面 查看原题

Polycarp 手机上的联系人中有 n 个电话号码。每个数字都是一个 9 位整数,以非 0 的数字开头。所有数字都是不同的。

Polycarp 的手机上安装了最新版本的 Berdroid OS。如果输入某个号码,则会显示联系人中具有等于输入的数字序列的子字符串的所有号码。例如,Polycarp的联系人中有三个电话号码:123456789、100000000和100123456,则:

- 如果他输入 00 将显示两个数字:100000000 和 100123456,
- 如果他输入 123,两个数字将显示 123456789 和 100123456,
- 如果他输入01,则只有一个数字100123456。

对于 Polycarp 联系人中的每个电话号码,找到长度最小的数字序列,这样如果 Polycarp 输入此序列,Berdroid 将显示唯一的电话号码。

输入

第一行包含单个整数 n (1 ≤ n ≤ 70000) — Polycarp 联系人中的电话联系人总数。

随后是电话号码,每行一个。每个数字都是以 1 到 9 的数字开头的 9 位正整数。所有数字都是不同的。

输出

精确打印 n 行:其中第 i 行应包含最短的非空数字序列,这样如果 Polycarp 输入它,Berdroid 操作系统将仅显示联系人中的第 i 个数字。如果有多个这样的序列,则打印其中任何一个。

示例

输入 #1

3
123456789
100000000
100123456

输出 #1

9
000
01

输入 #2

4
123456789
193456789
134567819
934567891

输出 #2

2
193
81
91