ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

2077. Сокращения

Ограничение времени: 0.5 секунды
Ограничение памяти: 32 МБ
Ограничение на язык: C, C++, Pascal
Даны слова, нужно записать каждое из них одним из трёх способов:
  1. Записать слово целиком.
  2. Записать префикс слова с точкой в конце.
  3. Записать префикс и суффикс слова и дефис между ними.
Будем называть новую запись сокращением слова и говорить, что слово подходит под сокращение, если дефис или точку можно заменить на некоторую строку (возможно, пустую) так, чтобы получить данное слово.
Требуется записать каждое слово так, чтобы под его сокращение подходило только данное слово.
Например, если даны слова «информация» и «индульгенция», то ни одно из них нельзя записать как «ин-я», так как под это сокращение подходят оба слова. Но можно записать их «инф.» и «инд.». Если даны слова «бар» и «барс», то их нельзя записать как «бар.», но можно записать как «бар» и «б-с» соответственно.
Из всех возможных способов записать слова нужно выбрать такой, чтобы суммарная длина сокращений была минимальной. Если таких способов несколько, то среди них нужно выбрать тот, в котором максимальное количество слов записано целиком. Если и таких способов несколько, то из них следует выбрать тот, в котором минимальное количество слов сокращено через дефис. Наконец, если и таких окажется несколько, то нужно максимизировать суммарную длину префиксов слева от дефиса. Гарантируется, что этим условиям удовлетворяет только один способ записи слов.

Исходные данные

В первой строке дано количество слов n (1 ≤ n ≤ 1 000 000). В следующих n строках перечислены слова. Все слова различны и состоят из строчных латинских букв, а их суммарная длина не превышает 1 000 000. Слова на входе отсортированы лексикографически.

Результат

Выведите список сокращений в том же порядке, в котором соответствующие слова были даны во входных данных.

Примеры

исходные данныерезультат
4
aba
abaca
add
dd
aba
a-ca
add
dd
2
aa
aaaaa
aa
aaa.
2
abc
abcdabc
abc
abcd.
Автор задачи: Михаил Рубинчик (Подготовка — Егор Щелконогов)