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:
  1. adding a letter to the end of the current word
  1. removing the last letter if there is one
  1. 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.8 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in