Impressora de tipos móveis

Tem uma impressora de tipos móveis, um dispositivo de impressão antigo que requer a disposição de pequenas peças de metal com letras para formar palavras. Esta impressora permite três operações:

1. adicionar uma letra ao final da palavra atual

2. remover a última letra, se existir

3. imprimir a palavra atual

O seu objetivo é escrever um programa que recebe como entrada n palavras e determina o número mínimo de operações necessário para imprimir todas as palavras em qualquer ordem. Além disso, o programa deve produzir uma sequência de operações que alcance esse mínimo.

Entrada

A primeira linha da entrada contém um único inteiro n (1 ≤ n ≤ 25,000), representando o número de palavras a imprimir.

Em seguida, surgem n linhas, cada uma contendo uma palavra formada por letras minúsculas ('a' - 'z') e com comprimento entre 1 e 20 (inclusive). Todas as palavras serão distintas.

Saída

O programa deve imprimir um inteiro m, que representa o número mínimo de operações necessárias para imprimir as palavras.

Nas m linhas seguintes, cada uma deve conter um único carácter que descreva a sequência de operações. As operações devem ser representadas da seguinte forma:

• Adicionar uma letra é representado pela própria letra minúscula.

• Remover a última letra é representado pelo carácter - (hífen, código ASCII 45).

• Imprimir a palavra atual é representado pelo carácter P (letra maiúscula P).

Exemplos