Pentru scrierea mesajelor soldaţii dintr-o unitate militară folosesc 9 litere mici: a, e, i, o, u, m, n, r, s şi caracterul spaţiu. Aceste litere sunt codificate cu ajutorul cifrelor 1, 2, ..., 9 (în ordinea de mai sus), iar pentru caracterul spaţiu se foloseşte cifra 0. Astfel codificarea textului ana are mere se poate realiza prin numărul natural 171018206282.
Pentru a mări gradul de securitate a mesajelor transmise soldaţii realizează o supracodificare, înlocuind fiecare cifră k folosită la codificare cu puterea 2k. Astfel textul anterior se supracodifică astfel: 2128212256416442564.
Cerinţă
Să se scrie un program care pentru o supracodificare dată, determină textul iniţial. Dacă există mai multe astfel de texte se vor determina toate.
Date de intrare
Fişierul de intrare codif.in conţine pe prima linie, n numărul de cifre folosite la textul supracodificat, iar pe a doua linie conţine supracodificarea.
Date de ieşire
Fişierul de ieşire codif.out va conţine pe prima linie numărul m de texte ce corespund supracodificării date, iar pe următoarele m linii, textele, fiecare dintre acestea pe câte o linie, în ordine lungo-lexicografică.
Restricţii
• 0< n < 83
• Pentru două texte u=u1u2...ua şi v=v1v2...vb, avem că u este înaintea lui v în ordine lungo-lexicografică, dacă a<b sau dacă a=b şi există un indice 1≤i≤a cu proprietatea că u1=v1,...,ui-1=vi-1, ui<vi. Ordinea caracterelor este cea dată de codurile ASCII. De exemplu, în ordine lungo-lexicografică, textul aerss este înaintea textului aeumr, şi după textul sun.
• Fiecare linie din fişierul de ieşire va avea sfârşit de linie.
• Pentru toate testele numărul de texte care corespunde aceleiaşi supracodificări este mai mic sau egal cu 70.
Exemple
codif.in
codif.out
19
2128212256416442564
4
ana are mere
ana areoeere
a aia are mere
a aia areoeere