CF858D Polycarp's phone book

Polycarp 的手机通讯录中有 $n$ 个电话号码。每个号码是一个 9 位数的正整数，且首位不为 $0$。所有号码互不相同。 Polycarp 的手机上装有最新版的 Berdroid 操作系统。当输入一串数字时，系统会显示出所有包含该数字序列作为子串的通讯录号码。例如，若通讯录里有三个号码：$123456789$、$100000000$ 和 $100123456$，则： - 如果他输入 $00$，会显示两个号码：$100000000$ 和 $100123456$； - 如果他输入 $123$，会显示两个号码：$123456789$ 和 $100123456$； - 如果他输入 $01$，只有一个号码会显示：$100123456$。 对于通讯录里的每一个电话号码，请找出一段最短的数字序列，使得 Polycarp 输入它时，Berdroid 只会显示这一号码。如果存在多种方案，任意输出其中一种即可。

第一行包含一个整数 $n$（$1\leq n \leq 70000$），表示通讯录中总共有多少个号码。 接下来 $n$ 行，每行包含一个电话号码。每个号码是一个首位为 $1$ 到 $9$ 的 9 位正整数。所有号码互不相同。

输出恰好 $n$ 行，第 $i$ 行应输出一个最短的非空数字序列，使得 Polycarp 输入它时，只有第 $i$ 个号码会被 Berdroid 系统显示。如果存在多解，输出任意一种即可。

由 ChatGPT 5 翻译