Mobile Printer Optimization

You are given an old‐fashioned mobile printer that prints words using small metal blocks with letters. Initially, the printer is empty. The printer supports the following operations:

• Add a letter at the end of the current word.
• Remove a letter from the end of the current word (only if there is at least one letter).
• Print the current word.

You are also given an integer $n$ and $n$ words. You may print the words in any order. The cost (number of operations) to print a word from the current word s to the target word t is given by:

cost(s,t)= (|s| - LCP(s,t)) + (|t| - LCP(s,t)) + 1,

where LCP(s,t) is the length of the longest common prefix of s and t. For the initial word, assume s is empty so the cost is |t|+1. Note that after finishing printing all words, leftover letters in the printer are allowed.

Your task is to determine a sequence of operations that prints all the words using the minimum number of operations, and output one valid optimal sequence.

inputFormat

The first line contains an integer $n$ ($1 \le n \le 10$), the number of words. Each of the next $n$ lines contains a word consisting of lowercase letters.

outputFormat

Output the minimum number of operations on the first line. Then, output the sequence of operations, one per line. Each operation is either:

• a lowercase letter (to add that letter),
• '-' (to remove the last letter), or
• 'P' (to print the current word).

This operation sequence should print all the given words (in any order) with the minimum total number of operations.

sample

3
bat
rat
cat

18
b
a
t
P




r
a
t
P




c
a
t
P