Даны слова, нужно записать каждое из них одним из трёх способов:

1. Записать слово целиком.
2. Записать префикс слова с точкой в конце.
3. Записать префикс и суффикс слова и дефис между ними.

Будем называть новую запись сокращением слова и говорить, что слово подходит под сокращение, если дефис или точку можно заменить на некоторую строку (возможно, пустую) так, чтобы получить данное слово.

Требуется записать каждое слово так, чтобы под его сокращение подходило только данное слово.

Например, если даны слова «информация» и «индульгенция», то ни одно из них нельзя записать как «ин-я», так как под это сокращение подходят оба слова. Но можно записать их «инф.» и «инд.». Если даны слова «бар» и «барс», то их нельзя записать как «бар.», но можно записать как «бар» и «б-с» соответственно.

Из всех возможных способов записать слова нужно выбрать такой, чтобы суммарная длина сокращений была минимальной. Если таких способов несколько, то среди них нужно выбрать тот, в котором максимальное количество слов записано целиком. Если и таких способов несколько, то из них следует выбрать тот, в котором минимальное количество слов сокращено через дефис. Наконец, если и таких окажется несколько, то нужно максимизировать суммарную длину префиксов слева от дефиса. Гарантируется, что этим условиям удовлетворяет только один способ записи слов.

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

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