Вам нужно напечатать N слов на Movable Type Printer. Movable Type Printers — это старые принтеры, для работы которых требуется ставить маленькие металлические кусочки (каждый из кусочков содержит одну букву) в определенном порядке, образуя таким образом слова. Потом все они вдавливаются в лист бумаги. Таким образом печатается одно слово. Ваш принтер позволяет делать следующие операции:
- Добавить букву в конец слова, находящегося сейчас на принтере.
- Удалить последнюю букву из слова, находящегося сейчас на принтере. Эту операцию можно делать, только если слово содержит хотя бы одну букву.
- Напечатать слово, находящееся на принтере.
Изначально на принтере содержится пустое слово. В конце печати на принтере можно оставить непустое слово. Слова, которые вам даны, вы можете печатать в произвольном порядке.
Каждая из трёх операций занимает одну единицу времени. Вам нужно найти последовательность операций, которая печатает данные N слов за минимальное время. Если минимальных последовательностaей несколько, выведите любую.
Входные данные
Ваша программа должна считать следующие входные данные:
На первой строке число N (1<=N<=25000).
На следующих N строках слова, состоящие из маленьких букв латинского алфавита. Длина каждого слова не превышает 20. Все слова различны.
Выходные данные
Ваша программа должна вывести следующие данные:
На первой строке M — число операций.
На следующих M строках по одному символу — описание операций. Каждая операция описывается одним символом:
Добавление символа обозначается собственно символом.
Удаление символа обозначается символом «-» (минус, ASCII-код 45).
Операция «напечатать текущее слово» обозначается символом «P» (заглавная латинская буква P).
| Ввод |
Вывод |
|
3
print
the
poem
|
20
t
h
e
P
-
-
-
p
o
e
m
P
-
-
-
r
i
n
t
P
|