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

2. removing the last letter if there is one

3. 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