Problem description

Jasio wymyślił bardzo “sprytną” (albo raczej głupią) metodę kodowania napisów. Literka a dostaje kod 1, literka b kod 2, literka z kod 26 (Jasio zna jedynie małe litery alfabetu angielskiego). Uzyskane kody Jasio skleja ze sobą i otrzymuje kodowanie całego napisu. W ten sposób słowo olimpiada otrzymuje kod 1512913169141. Oczywiście kodowanie nie jest jednoznaczne, ale o tym Jasio nie pomyślał wcześniej.

Otrzymałeś od Jasia zakodowany napis. Co on mógł oznaczać? Napisz program, który wczyta kodowanie Jasia, wyznaczy wszystkie możliwe napisy, które mogły uzyskać takie kodowanie i wypisze je w kolejności leksykograficznej.

Wejście

W pierwszym (jedynym) wierszu wejścia znajduje się ciąg cyfr (bez żadnych odstępów) – kodowanie pewnego napisu uzyskane metodą Jasia.

Wyjście

Twój program powinien wypisać na wyjście wszystkie napisy, które prowadzą do uzyskania kodowania z wejścia. Napisy mają być wypisane w osobnych wierszach, w kolejności leksykograficznej.

Ograniczenia

Długość ciągu cyfr podanego na wejściu nie przekracza 1 000 znaków. Ponadto, liczba napisów, które należy wypisać nie przekracza 50 000.

Przykład

261411495

bfadaadie
bfadanie
bfadkdie
bfnaadie
bfnanie
bfnkdie
zadaadie
zadanie
zadkdie
znaadie
znanie
znkdie