POLSKI SPOJ

W ramach proekologicznej akcji pod hasłem "szanuj lasy, oszczędzaj papier", Jaś postanowił ograniczyć zużycie papieru w procesie swojej edukacji. Niestety, jego pierwszy pomysł polegający na nieodrabianiu prac domowych spotkał się ze zdecydowaną dezaprobatą nauczycieli. Dlatego też zasmucony Jaś ograniczył się tylko do kompresji pracy domowej i potrzebuje w tym celu Twojej pomocy.

Twoim zadaniem jest skompresowanie podanego na wejściu tekstu pracy domowej, złożonego wyłącznie z małych liter alfabetu 'a'-'z'. Postać skompresowana musi być czytelna dla dekompresora (w który wyposażony został każdy nauczyciel Jasia).

Dekompresor przetwarza tekst znak po znaku, interpretując poszczególne znaki jako polecenia zgodnie z następującymi zasadami:

• znak 'a'-'z': wypisz napotkaną literę,
• znak '+', po którym następuje liczba naturalna n: wypisz ponownie n ostatnio wypisanych liter,
• znak '-', po którym następuje liczba naturalna n: wymaż n ostatnio wypisanych liter.

Wartość liczby n nigdy nie może przekroczyć liczby dotychczas wypisanych znaków, a łączna liczba wymazywanych znaków nie może przekroczyć trzykrotności długości dekompresowanego pliku.

Wejście

Na wejściu podany jest ciąg znaków 'a'-'z' zakończony znakiem nowej linii, nie dłuższy niż 10⁵ znaków.

Wyjście

Na wyjściu należy wypisać ciąg znaków w skompresowanej postaci. Postać skompresowana musi spełniać założenia podane w treści zadania.

Wynik

Liczba punktów przyznanych za rozwiązanie zadania jest równa stosunkowi długości tekstu skompresowanego do długości tekstu zdekompresowanego.

Przykład

Wejście:
abcabcabcabdddddd

Wyjście:
abc+3+6-1ddd+3

Wynik:
0.824