eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Наборный принтер

Наборный принтер

Лимит времени 4 секунды
Лимит использования памяти 64 MiB

Вам необходимо напечатать N слов на наборном принтере. Наборный принтер - это такой старый принтер, в который требуется устанавливать маленькие металлические элементы (каждый из которых содержит букву) для того, чтобы формировать слова. После этого к ним прижимается лист бумаги, чтобы отпечатать слово. Ваш принтер позволяет выполнять следующие операции:

  1. Добавлять букву в конец слова, которое набрано в принтере.

  2. Удалять последнюю букву из слова, которое набрано в принтере. Это можно делать только в том случае, когда в принтере установлена хотя бы одна буква.

  3. Печатать слово, набранное в принтере.

Вначале принтер пуст: он не содержит металлических элементов с буквами. По окончании печати разрешается оставлять в принтере некоторые буквы. Также можно печатать слова в любом порядке, который вам нравится.Поскольку каждая операция занимает некоторое время, вы хотите минимизировать общее количество операций.

Вы должны написать программу, которая по заданным N словам находит минимальное количество операций, необходимых для печати всех этих слов в любом порядке, и выводит одну из таких последовательностей операций.

1 <= N <= 25 000 (N - Количество слов, которые необходимо напечатать)

Входные данные

Ваша программа должна читать из стандартного ввода следующие данные:

  1. Строка 1 содержит целое число N - количество слов, которые необходимо напечатать.

  2. Каждая из последующих N строк содержит слово. Каждое слово состоит только из маленьких латинских букв ('a' - 'z') и имеет длину от 1 до 20 символов, включительно.

Все слова различны.

Выходные данные

Ваша программа должна вывести в стандартный вывод следующие данные:

  1. Строка 1 должна содержать целое число M, которое означает минимальное количество операций, требуемых для печати N слов.

  2. Каждая из последующих M строк должна содержать по одному символу. Эти символы описывают последовательность выполняемых операций. Каждая операция должна быть описана следующим образом:

  3. Добавление буквы обозначается самой буквой, набранной в нижнем регистре

  4. Удаление последней буквы обозначается символом '-' (минус, ASCII код 45)

  5. Печать текущего слова обозначается символом 'P' (большая латинская буква P)

Пример

Входные данные #1
3
print
the
poem
Выходные данные #1
20
t
h
e
P
-
-
-
p
o
e
m
P
-
-
-
r
i
n
t
P