Задача №114311. Везувий
Члены комиссии соревнования ICPC не смогли придумать задачи, поэтому они решили ранжировать команды лексикографически. Таким образом, победителем станет команда, название которой лексикографически самое маленькое. Героиня этой задачи, Этна, является лидером команды, личность которой мы будем скрывать. Название её команды начинается с буквы «Z», что ставит её в довольно плохое положение. После долгих разговоров с комитетом Этна смогла добиться более справедливого способа ранжирования команд. К сожалению, команды будут продолжать сортировать лексикографически, но определение лексикографического порядка изменится. А именно, комитет случайным образом выберет перестановку букв английского алфавита и определит лексикографический порядок, используя эту перестановку. Этна сразу же достала свой ноутбук и написала программу, которая находит перестановку букв для каждой команды, согласно которой эта команда выиграет соревнование. К сожалению, программа еще не закончена. Помогите Этне и напишите более эффективную программу с той же функциональностью.
На первной строке дано натуральное число \(N\), которое обозначает количество команд, участвующих в соревновании.
В следующих \(N\) строках даны названия команд, участвующих в соревновании. Название каждой команды состоит из одного слова, которое в свою очередь состоит из строчных букв английского алфавита. Конечно, названия команд отличаются друг от друга.
Для каждой команды в исходном порядке необходимо вывести перестановку букв английского алфавита, в соответствии с которой эта команда выиграет соревнование. Если такой перестановки нет, необходимо вывести слово «nemoguce», а если таких перестановок несколько, достаточно вывести любую.
В этой задаче 3 подгруппы. Обозначим \(L\) - суммарную длину строк, \(K\) - количество различных букв.
(13 баллов) \(1 \le N \le 100, 1 \le L \le 10000, 1 \le K \le 6\)
(32 балла) \(1 \le N \le 350, 1 \le L \le 10000, 1 \le K \le 26\)
(55 баллов) \(1 \le N \le 25000, 1 \le L \le 1000000, 1 \le K \le 26\)
3 war zag wro
yxwzvutsqponmlkjihgfedcbar zyxwvutsrqponmlkjihgfedcba yxwzvutsrqponmlkjihgfedcba
3 b ab aa
zyxwvutsrqponmlkjihgfedcba nemoguce zyxwvutsrqponmlkjihgfedcab
7 bcada dbaab bbabc ababb aacdf bcdff baddb
zyxwvutsrqponmlkjihgfecbad zyxwvutsrqponmlkjihgfedcba zyxwvutsrqponmlkjihgfebdca nemoguce zyxwvutsrqponmlkjihgfecadb zyxwvutsrqponmlkjihgfecbda nemoguce