Задача №114142. Васянский словарь
Вася и его друзья давно мечтали придумать свой язык, чтобы никто из взрослых не понимал о чём они между собой разговаривают. После нескольких месяцев кропотливой работы ребята подготовили васянский словарь, но, как это часто бывает в задачах по программированию, появился второстепенный персонаж легенды Петя (брат Васи) и перемешал буквы в некоторых словах словаря, когда Вася вышел из комнаты.
Помогите Васе восстановить словарь, ведь он потратил на его составление огромное количество времени. Вася помнит, что слова в словаре были перечислены в лексикографическом порядке, то есть каждое следующее слово было не меньше предыдущего лекскикографически (при этом они могли быть равны). Его устроит любой словарь, удовлетворяющий этом свойству.
Вам требуется по заданному списку слов так переставить буквы в каждом из них, чтобы в полученной последовательности слова стояли в лексикографическом порядке, либо определить, что это невозможно.
В первой строке входных данных записано единственное число n ( 1 ≤ n ≤ 200 000 ) — количество слов в васянском словаре.
В i -й из последующих n строк записано слово s i , состоящее из строчных английских букв — i -я запись в словаре после того как Петя уже поменял некоторые буквы местами (возможно, что в некоторых словах все буквы остались на своих местах).
Гарантируется, что суммарная длина всех слов не превосходит 1 000 000 , и что все слова состоят из хотя бы одной буквы.
Выведите n слов, по одному в каждой строке, описывающих какой-нибудь словарь, который устроит Васю. Должно быть возможно получить i -е из этих слов произвольной перестановкой букв из слова s i . Разрешается оставлять некоторые слова без изменения.
Если не существует способа переставить буквы в некоторых словах местами так, чтобы список слов стал отсортированным лексикографически, то выведите - 1 .
Слово a 1 , a 2 , ..., a m длины m лексикографически не превосходит слова b 1 , b 2 , ..., b k длины k , если выполняется одно из двух:
- либо в первой позиции i , такой что a i ≠ b i , символ a i идёт раньше по алфавиту, чем символ b i , то есть в первой различающейся позиции символ слова a меньше символа слова b ;
- либо (если такой позиции нет) m ≤ k , то есть второе слово начинается с первого либо совпадает с ним.
Тесты к этой задаче состоят из трёх групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.
4 ab baa bab bba
ab aba abb abb
4 ab abab aaab aaaaa
-1