Члены жюри одного регионального соревнования ICPC не смогли обеспечить надлежащие условия для проведения состязания, поэтому решили ранжировать команды лексикографически. Таким образом, победителем будет объявлена команда, чье название является лексикографически наименьшим.
Героиня этой задачи, Этна, является руководителем команды, чье название мы скроем, но достаточно сказать, что это команда, название которой начинается с буквы ‘Z’, что ставит её в довольно невыгодное положение. После долгих дискуссий с жюри Этна смогла добиться более справедливого способа ранжирования команд. К сожалению, команды по-прежнему будут ранжироваться лексикографически, но определение лексикографического порядка изменится. Точнее, жюри случайным образом выберет некоторую перестановку букв английского алфавита и естественным образом определит лексикографический порядок с помощью этой перестановки. Иными словами, порядок букв в перестановке будет соответствовать их лексикографическому порядку.
Этна сразу же достала свой ноутбук и написала программу, которая для каждой команды находит такую перестановку букв, при которой именно эта команда выиграет соревнование. К сожалению, программа до сих пор не завершила выполнение. Помогите Этне и напишите более эффективную программу с той же функциональностью.
Входные данные
В первой строке содержится натуральное число $N$, представляющее количество команд, участвующих в соревновании.
В следующих $N$ строках содержатся названия команд, участвующих в соревновании. Название каждой команды состоит из одного слова, которое, в свою очередь, состоит из строчных букв английского алфавита. Разумеется, названия команд различны.
Выходные данные
Для каждой команды, в порядке их следования во входных данных, необходимо вывести в отдельной строке перестановку букв английского алфавита, при которой эта команда выиграет соревнование. Если такой перестановки не существует, необходимо вывести слово “nemoguce”, а если существует несколько таких перестановок, достаточно вывести любую из них.
Подзадачи
Пусть $L$ — сумма длин слов всех $N$ команд, а $K$ — количество различных букв, встречающихся в названиях всех команд.
| Подзадача | Количество баллов | Ограничения |
|---|---|---|
| 1 | 13 | $1 \le N \le 100, 1 \le L \le 10\,000, 1 \le K \le 6$ |
| 2 | 32 | $1 \le N \le 350, 1 \le L \le 10\,000, 1 \le K \le 26$ |
| 3 | 55 | $1 \le N \le 25\,000, 1 \le L \le 1\,000\,000, 1 \le K \le 26$ |
Примеры
Входные данные 1
3 war zag wro
Выходные данные 1
agorwzbcdefhijklmnpqstuvxy agorzwbcdefhijklmnpqstuvxy gorawzbcdefhijklmnpqstuvxy
Входные данные 2
3 b ab aa
Выходные данные 2
bacdefghijklmnopqrstuvwxyz nemoguce abcdefghijklmnopqrstuvwxyz
Входные данные 3
7 bcada dbaab bbabc ababb aacdf bcdff baddb
Выходные данные 3
cbadfeghijklmnopqrstuvwxyz cdabfeghijklmnopqrstuvwxyz bacdfeghijklmnopqrstuvwxyz nemoguce abcdfeghijklmnopqrstuvwxyz cbdafeghijklmnopqrstuvwxyz nemoguce