Movable Type Printer
You have a movable type printer, an old printing device that requires arranging small metal pieces with letters to form words. The printer allows three operations:
- adding a letter to the end of the current word
- removing the last letter if there is one
- printing the current word.
Your task is to write a program that takes as input
n words and finds the minimum number of operations required to print all the words in any order. Additionally, the program should output a sequence of operations that achieves this minimum.Input
The first line of the input contains a single integer
n (1 ≤ n ≤ 25,000) representing the number of words to print.It is followed by
n lines, each containing a word consisting of lowercase letters ('a' - 'z') with a length between 1 and 20 (inclusive). All words will be distinct.Output
The program should print an integer
m representing the minimum number of operations required to print the words.The next
m lines should each contain one character to describe the sequence of operations. The operations should be represented as follows:- Adding a letter is represented by the lowercase letter itself.
- Removing the last letter is represented by the character
-(minus, ASCII code 45).
- Printing the current word is represented by the character
P(uppercase letter P).
Examples
Input | Output |
3
print
the
poem | 20
t
h
e
P
-
-
-
p
o
e
m
P
-
-
-
r
i
n
t
P |
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB