Problem
Você precisa imprimir N palavras na Movable Type Printer. Impressoras de tipos móveis — são impressoras antigas que exigem que pequenos pedaços de metal (cada pedaço contendo uma letra) sejam colocados em uma determinada ordem para formar palavras. Então eles são todos pressionados em uma folha de papel. Isso imprime uma palavra. Sua impressora permite que você faça o seguinte:
- Adicione uma letra ao final da palavra atualmente na impressora.
- Remova a última letra da palavra atualmente na impressora. Esta operação só pode ser realizada se a palavra contiver pelo menos uma letra.
- Imprima a palavra atualmente na impressora.
Inicialmente, a impressora contém uma palavra vazia. Você pode deixar uma palavra não vazia no final da impressão na impressora. Você pode digitar as palavras fornecidas em qualquer ordem.
Cada uma das três operações leva uma unidade de tempo. Você precisa encontrar uma sequência de operações que imprima as N palavras dadas no mínimo de tempo. Se houver várias sequências mínimas, imprima qualquer uma.
Entrada
Seu programa deve receber a seguinte entrada:
Na primeira linha está o número N (1<=N<=25000).
Nas próximas N linhas, palavras que consistem em letras minúsculas do alfabeto latino. O comprimento de cada palavra não excede 20. Todas as palavras são diferentes.
Saída
Seu programa deve gerar o seguinte:
Na primeira linha M — número de operações.
Nas próximas M linhas, uma — descrição das operações. Cada operação é descrita por um único caractere:
Adicionar um caractere é indicado pelo próprio caractere.
A exclusão de um caractere é indicada pelo caractere "-" (menos, código ASCII 45).
A operação "imprimir a palavra atual" denotado pelo símbolo «P» (letra P maiúsculo).
| Entrada |
Saída |
|
3
imprimir
o
poema
|
20
t
h
e
P
-
-
-
p
o
e
m
P
-
-
-
r
i
n
t
P
|