English version is in beta. All contents of the site should be already translated (mostly using machine translation), and everything should work properly. However, if you find any problems, please contact me.
The problem statement has been automatically translated from Russian. If the statement is not clear, or you have any comments about it, please contact me. Anyway, I hope that someday I will fix the translation manually.

Type Printer

You need to print \(N\) words on a Movable Type Printer. Movable Type Printers are old printers whose operation requires putting small metal pieces (each of the pieces contains one letter) in a certain order, thus forming words. Then they are all pressed into a piece of paper. One word is printed this way. Your printer allows you to do the following operations:

  • Add a letter to the end of the word currently on the printer.
  • Delete 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 a word that is on the printer (while the word is nowhere does not disappear, you can print it again and again).

Initially, the printer contains an empty word. At the end of printing on the printer , you can leave a non-empty word. The words that are given to you, you can type in any order.

Each of the three operations takes one unit of time. You need to find a sequence of operations that prints data \(N\) words in minimum time. If there are several minimum sequences, output any one.

Input data

Your program should read the following input data:

  • On the first line is the number \(N\) (\(1\le N\le 25\,000\)).
  • On the following \(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 data

Your program should output the following data:

  • On the first line \(M\) is the number of operations.
  • On the following \(M\) lines, one character each is a description of the operations. Each operation is described by one character:
    • The addition of a symbol is indicated by the actual symbol.
    • Deleting a character is indicated by the "-" symbol (minus, ASCII code 45).
    • The operation "print the current word" is indicated by the symbol "P" (capital Latin letter P).
Examples
Input data
3
print
the
poem
Output data
20
t
h
e
P
-
-
-
p
o
e
m
P
-
-
-
r
i
n
t
P

This problem on informatics

algoprog.ru © Petr Kalinin, GNU AGPL, github.com/petr-kalinin/algoprog | About the license for the site materials | Blog (in Russian)