Вася ведёт публичную страницу организации “Мышь и клавиатура”, где постоянно публикует различные новости из мира спортивного программирования. Для удобства поиска по новостям Вася прикрепляет к каждой из них список хештегов. В данной задаче хештегом называется строка, состоящая из маленьких букв английского алфавита и ровно одного символа ‘#’, расположенного в начале строки. Длиной хештега будем называть количество символов в нём, без учёта символа ‘#’.
Начальство Васи распорядилось, что хештеги у каждой новости должны быть расположены в лексикографическом порядке (для пояснения смотрите примечания).
Поскольку вам не хочется менять порядок хештегов в уже написанной новости, вы решили удалить у некоторых хештегов некоторый суффикс (какое-то количество последних символов), при этом можно даже удалить весь текст хештега, оставив только символ ‘#’, но сам символ ‘#’ удалять нельзя. Из всех возможных вариантов такого удаления вы хотите выбрать тот, в котором суммарно будет удалено минимальное количество символов. Если и таких вариантов несколько, то разрешается использовать любой из них.
Формат входных данных
В первой строке находится одно число \(n\) (\(1 \leq n \leq 500\,000\)) — количество хештегов в новости.
Каждая из следующих \(n\) строк содержит ровно один хештег положительной длины.
Обозначим через \(L\) суммарную длину всех хештегов. Гарантируется, \(L\) не превосходит \(500\,000\).
Формат выходных данных
Выведите полученные после удаления символов хештеги.
Замечание
Слово \(a_1, a_2, \ldots, a_m\) длины \(m\) лексикографически меньше слова \(b_1, b_2, \ldots, b_k\) длины \(k\), если выполняется одно из двух:
-
либо в первой позиции \(i\), такой что \(a_i \neq b_i\), символ \(a_i\) идёт раньше по алфавиту, чем символ \(b_i\), то есть в первой различающейся позиции символ слова \(a\) меньше символа слова \(b\);
-
либо (если такой позиции нет) \(m < k\), то есть второе слово начинается с первого, но при этом не совпадает с ним.
Про последовательность слов говорят, что они идут в лексикографическом порядке, если каждое слово в нём (кроме последнего) лексикографически не превосходит следующее за ним.
Для слов, состоящих из маленьких латинских букв, лексикографический порядок совпадает с алфавитным порядком расположения слов в словаре.
Слово, состоящее только из символа ‘#’, лексикографически меньше любого другого хештега. Поэтому в третьем примере мы не можем оставить два первых слова и сократить два вторых.
В данной задаче 50 тестов, помимо тестов из условия, каждый из них оценивается в 2 балла. Результаты работы ваших решений на первых 35 тестах будут доступны во время соревнования. Результаты работы на остальных 15 будут доступны после окончания соревнования.
Решения, корректно работающие при \(1 \leq n, L \leq 15\), наберут не менее \(20\) баллов.
Решения, корректно работающие при \(1 \leq n, L \leq 1\,000\), наберут не менее \(50\) баллов.
Решения, корректно работающие при \(1 \leq n, L \leq 100\,000\), наберут не менее \(70\) баллов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
#book
#bigtown
#big
|
#b
#big
#big
|
|
2
|
3
#book
#cool
#cold
|
#book
#co
#cold
|
|
3
|
4
#car
#cart
#art
#at
|
#
#
#art
#at
|
|
4
|
3
#apple
#apple
#fruit
|
#apple
#apple
#fruit
|