Problem
You need to print N words on Movable Type Printer. Movable Type Printers — they are old printers that require small pieces of metal (each piece containing one letter) to be placed in a certain order to form words. Then they are all pressed into a sheet of paper. This prints one word. Your printer allows you to do the following:
- Add a letter to the end of the word currently on the printer.
- Remove the last letter from the word currently on the printer. This operation can be done only if the word contains at least one letter.
- Print the word currently on the printer.
Initially, the printer contains an empty word. You can leave a non-empty word at the end of printing on the printer. You can type the words you are given in any order.
Each of the three operations takes one unit of time. You need to find a sequence of operations that prints the given N words in the minimum amount of time. If there are several minimal sequences, print any one.
Input
Your program should take the following input:
On the first line is the number N (1<=N<=25000).
On the next N lines, words consisting of small letters of the Latin alphabet. The length of each word does not exceed 20. All words are different.
Output
Your program should output the following:
On the first line M — number of operations.
On the next M lines, one — description of operations. Each operation is described by a single character:
Adding a character is indicated by the character itself.
Deleting a character is indicated by the character "-" (minus, ASCII code 45).
The "print current word" operation denoted by the symbol «P» (capital Latin letter P).
| Input |
Output |
|
3
print
the
poem
|
20
t
h
e
P
-
-
-
p
o
e
m
P
-
-
-
r
i
n
t
P
|