robot

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:

• Dp: Mânerul robotului se deplasează spre dreapta cu $p$ poziții ($p$ este o cifră)
• Sp: Mânerul robotului se deplasează spre stânga cu $p$ poziții ($p$ este o cifră)
• A: Este apăsat butonul în dreptul căruia se află mânerul robotului și pe ecran apare cifra scrisă pe buton
• T: Terminarea programului (se utilizează o singură dată la final și este precedată de cel puțin o instrucțiune $A$)

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ță

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

• citește un roboprogram și determină numărul de cifre afișate pe ecran după executarea roboprogramului;
• citește un roboprogram și determină cifrele afișate pe ecran după executarea roboprogramului;
• 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 deplasare minimă, se va afișa roboprogramul cu număr maxim de instrucțiuni $D$.

Date de intrare

Fișierul de intrare robot.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 robot.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 \leq N \leq 10^9$;
• 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

robot.in

1
D1AD2AS1AT

robot.out

3

Explicație

$C = 1$, pentru acest test se rezolvă cerința $1$.

Se afișează pe ecran $3$ cifre ($132$)

Exemplul 2

robot.in

2
S0AD2AS1AT

robot.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

robot.in

3
19332

robot.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