Drukarka

Limit pamięci: 64 MB

Musisz wydrukować słów. Twoja drukarka to stary model, który obsługuje się, składając słowo z czcionek - odlanych z metalu małych elementów, z których każdy zawiera jedną literę. Do tak ułożonego wzoru przykłada się kartkę papieru, aby wydrukować złożone słowo. Drukarka, którą posiadasz, pozwala na wykonanie każdej z następujących operacji:

• dodania jednej litery na końcu słowa znajdującego się aktualnie w drukarce;
• usunięcia ostatniej litery słowa znajdującego się aktualnie w drukarce;
• wydrukowania słowa znajdującego się aktualnie w drukarce.

Początkowo drukarka jest pusta; nie zawiera żadnych czcionek. Po zakończeniu pracy nie musisz czyścić drukarki - możesz pozostawić w niej dowolne czcionki. Ponadto, słowa możesz drukować w dowolnej kolejności.

Ponieważ każda z operacji wymaga pewnego czasu, chcesz zminimalizować łączną liczbę wykonanych operacji.

Zadanie

Napisz program, który mając danych słów, wyznaczy minimalną liczbę operacji potrzebnych do ich wydrukowania w dowolnej kolejności i wypisze jedną taką sekwencję operacji.

Ograniczenia

- liczba słów, które chcesz wydrukować.

Wejście

Twój program powinien wczytać ze standardowego wejścia następujące dane:

• Pierwszy wiersz zawierający liczbę całkowitą - liczbę słów do wydrukowania.
• Kolejnych wierszy, z których każdy zawiera jedno słowo. Każde słowo składa się wyłącznie z małych liter ('a' - 'z') i ma długość od 1 do 20 (włącznie). Wszystkie słowa są różne.

Wyjście

Twój program powinien wypisać na standardowe wyjście następujący wynik:

• Pierwszy wiersz powinien zawierać liczbę całkowitą oznaczającą minimalną liczbę operacji potrzebnych do wydrukowania danych słów.
• Każdy z kolejnych wierszy powinien zawierać jeden znak. Znaki te opisują sekwencję wykonanych operacji. Każda z nich musi być zapisana następująco:
  • dodanie małej litery jest reprezentowane przez nią samą,
  • usunięcie ostatniej litery jest reprezentowane przez znak '-' (minus, kod ASCII 45),
  • wydrukowanie aktualnego słowa jest reprezentowane przez znak 'P' (wielka litera P).

Punktacja

W testach wartych łącznie 40 punktów, wartość nie przekracza 18.

Przykład

Dla danych wejściowych:

3
print
the
poem

poprawną odpowiedzią jest:

20
t
h
e
P
-
-
-
p
o
e
m
P
-
-
-
r
i
n
t
P