30771번 - Рефераты 다국어

Флорен и её друзьям на уроке английского поручили подготовить рефераты по предоставленным статьям --- каждому ученику была выдана отдельная статья, по которой он должен сделать реферат. В рамках данной задачи статьёй называется непустая строка, состоящая из строчных символов английского алфавита. Рефератом статьи называется непустая строка, являющаяся подстрокой данной статьи. Все ученики должны будут представить свои рефераты у доски. Чтобы их было интереснее слушать, учитель потребовал, чтобы каждый из представленных рефератов не встречался как подстрока ни в одном тексте статьи, кроме той, из текста которой он был образован.

Так как Флорен и её друзья не любят тратить много времени на выполнение домашнего задания, они попросили вас помочь им выбрать для каждой статьи реферат минимальной длины, который не является подстрокой никакой другой статьи, либо сообщить, что выбрать реферат, удовлетворяющий требованию учителя, невозможно. Если для какого-то ученика возможно образовать несколько кратчайших рефератов, из них требуется выбрать лексикографически минимальный. Вы, конечно же, согласились им помочь.

В первой строке ввода записано одно число $n$ ($1 \leq n \leq 100\,000$) --- количество статей.

Следующие $n$ строк содержат описания статей. Каждая статья представляет собой последовательность строчных символов английского алфавита $s_i$ ($1 \leq |s_i| \leq 500\,000$).

Обозначим через $L$ суммарную длину всех статей, то есть $L = \sum\limits_{i = 1}^{n} |s_i|$. Гарантируется, что во всех тестах $L \leq 500\,000$.

Выведите $n$ строк --- рефераты, соответствующие указанным статьям, в том же порядке, что и во входных данных, или символ '?', если для статьи не существует подходящего реферата.

Пояснение к первому тесту из примеров.

Любая подстрока первой статьи полностью содержится в четвёртой, поэтому для первой статьи нет подходящего реферата. Во второй статье самыми короткими подходящими рефератами являются 'de', 'ee' и 'er', но лексикографически наименьшим из них является 'de'. В третьей статье самыми короткими подходящими рефератами являются 're' и 'ad', но лексикографически наименьшим из них является 'ad'. В четвёртой статье есть только один самый короткий подходящий реферат --- 'rd'.