Paul dorește să învețe cum să programeze un robot. Pentru început s-a gândit să construiască un robot format dintr-un mâner, 10 butoane aranjate circular şi un ecran. Pe butoane sunt scrise, în ordine crescătoare, cifrele de la 0 la 9, ca în figură.

Un roboprogram va fi format dintr-o secvenţă de instrucţiuni. Instrucțiunile pot fi:

Iniţial mânerul robotului este plasat în dreptul butonului 0, iar ecranul este gol.
De exemplu, în urma executării roboprogramului D4AS1AAD6AT robotul apasă butoanele pe care sunt scrise cifrele 4, 3, 3, 9, iar pe ecran va apărea 4339.

Cerințe

Să se scrie un program care rezolvă următoarele cerinţe:

1. citeşte un roboprogram şi determină numărul de cifre afişate pe ecran după executarea roboprogramului;
2. citeşte un roboprogram şi determină cifrele afişate pe ecran după executarea roboprogramului;
3. citeşte un număr natural N şi construieşte un roboprogram de lungime minimă prin executarea căruia pe ecran se va obţine numărul N; deoarece robotului îi place să se deplaseze în special spre dreapta, dacă există mai multe roboprograme de lungime minimă, se va afişa roboprogramul cu număr maxim de instrucţiuni D.

Date de intrare

Fişierul de intrare robot3.in conţine pe prima linie un număr natural C, reprezentând cerinţa care urmează să fie rezolvată (1, 2 sau 3). Dacă C=1 sau C=2, pe a doua linie a fişierului se află un roboprogram. Dacă C=3, pe a doua linie a fişierului de intrare se află numărul natural N.

Date de ieșire

Fişierul de ieşire robot3.out va conţine o singură linie. Dacă C=1, pe prima linie se va scrie un număr natural reprezentând numărul de cifre afişate pe ecran după executarea roboprogramului din fişierul de intrare.
Dacă C=2, pe prima linie vor fi scrise cifrele afișate pe ecran în urma executării roboprogramului din fişierul de intrare. Dacă C=3, pe prima linie va fi scris roboprogramul solicitat de cerinţa 3.

Restricții și precizări

• 0 ≤ N ≤ 1000000000
• Lungimea roboprogramului citit din fişierul de intrare sau scris în fişierul de ieşire este cel mult 1000 de caractere.
• Dacă mânerul este plasat în dreptul butonului 0 şi se deplasează spre dreapta, se va îndrepta către butonul 1; dacă deplasarea este spre stânga, se va îndrepta către butonul 9.
• Pentru rezolvarea corectă a primei cerinţe se acordă 10 puncte, pentru rezolvarea corectă a celei de a doua cerințe se acordă 30 de puncte, iar pentru rezolvarea corectă a celei de a treia cerințe se acordă 50 de puncte. 10 puncte se acordă din oficiu.

Exemplul 1:

robot3.in

1
D1AD2AS1AT

robot3.out

3

Explicație

C=1, pentru acest test se rezolvă cerința 1.
Se afişează pe ecran 3 cifre (132)

Exemplul 2:

robot3.in

2
S0AD2AS1AT

robot3.out

021

Explicație

C=2, pentru acest test se rezolvă cerința 2.
Mânerul robotului se deplasează cu 0 unități la stânga, deci rămâne în dreptul butonului 0 și apasă, apoi se deplasează 2 unități spre dreapta şi ajunge în dreptul butonului 2, apasă, apoi se deplasează 1 unitate la stânga și ajunge în dreptul butonului 1 și apasă acest buton → 021.

Exemplul 3:

robot3.in

3
19332

robot3.out

D1AS2AD4AAS1AT

Explicație

C=3, pentru acest test se rezolvă cerința 3. Pentru a afișa cifra 1, mânerul robotului se deplasează 1 unitate la dreapta după care apasă (D1A). Pentru a afișa cifra 9, din poziția curentă mânerul robotului se deplasează 2 unități la stânga şi apasă (S2A). Pentru a afișa cifra 3, din poziția curentă mânerul robotului se deplasează 4 unități la dreapta după care apasă (D4A). Pentru a afișa a doua cifra 3, mânerul robotului rămâne în poziția curentă și apasă butonul. Pentru a afișa cifra 2, din poziția curentă mânerul robotului se deplasează 1 unitate la stânga după care apasă (S1A). Programul se termină cu instrucțiunea T → D1AS2AD4AAS1AT