rotire25

George a primit ca temă la matematică următoarea problemă. Se dă un număr $X$, asupra acestui număr se pot face următoarele transformări:

1. În această ordine (toți acești $3$ pași reprezintă o transformare):
   • se înmulțește numărul cu $5$ (de exemplu: $X=416$ devine $416 \cdot 5 = 2080$)
   • se elimină toate zerourile din număr ($2080$ devine $28$)
   • se oglindește numărul ($28$ devine $82$)
2. În această ordine (toți acești $3$ pași reprezintă o transformare):
   • se înmulțește numărul cu $2$ (de exemplu: $X = 32$ devine $32 \cdot 2 = 64$)
   • se elimină toate zerourile din număr ($64$ rămâne $64$)
   • se oglindește numărul ($64$ devine $46$)

George trebuie să aplice alternativ cele două transformări asupra numărului $X$. Prima dată aplică transformarea $1$, apoi pe rezultatul obținut se aplică transformarea $2$, apoi pe rezultat se aplică iar transformarea $1$, apoi iar transformarea $2$ și așa mai departe. George trebuie să aplice asupra numărului $X$ exact $K$ transformări, în ordinea descrisă mai sus.

Cerință

Dându-se numerele $X$ și $K$ determinaţi:

1. Produsul dintre ultima cifră a numărului $X \cdot X \cdot X \cdot \ldots \cdot X$ (de $K$ ori) şi prima cifră a lui $X$.
2. Numărul rezultat după aplicarea celor $K$ transformări.

Date de intrare

Pe prima linie a fișierului de intrare rotire25.in se află trei numere separate prin câte un spațiu $C, X$ și $K$. Dacă $C=1$ se va rezolva doar prima cerință, iar dacă $C=2$ se va rezolva doar a doua cerință.

Date de ieșire

Fișierul de ieșire rotire25.out va conține un singur număr. Dacă $C = 1$, acest număr reprezintă rezultatul pentru prima cerinţă, iar dacă $C = 2$, acest număr reprezintă rezultatul pentru a doua cerință.

Restricții și precizări

• $1 \leq X \leq 999$;
• $1 \leq K \leq 1 \ 000 \ 000 \ 000$;
• Pentru teste în valoare de $29$ de puncte, $C = 1$.
• Pentru teste în valoare de $71$ de puncte, $C = 2$.
• Pentru teste în valoare de $7$ puncte, $C = 1$ și se garantează că numărul obținut în urma înmulțirilor este $\leq {10}^{18}$ ($1 \ 000 \ 000 \ 000 \ 000 \ 000 \ 000$).
• Pentru alte teste în valoare de $11$ puncte: $C = 1$ și $K \leq 100 \ 000$.
• Pentru teste în valoare de $39$ de puncte: $C = 2$ și $K \leq 100 \ 000$.
• Pentru alte teste în valoare de $9$ puncte: $C = 2$ și $X \leq 9$.

Exemplul 1

rotire25.in

1 27 3

rotire25.out

6

Explicație

Se rezolvă cerinţa $1$: $X = 27, K = 3$. $27 \cdot 27 \cdot 27 = 19 \ 683 \implies$ ultima cifră este $3$. Prima cifră a lui $27$ este $2$, deci rezultatul este $2 \cdot 3 = 6$

Exemplul 2

rotire25.in

2 13 3

rotire25.out

551

Explicație

Pentru al doilea exemplu, se rezolvă cerința $2$: $X = 13, K = 3$.
Se fac următoarele transformări:

• $13 \cdot 5 = 65$, scoatem zerourile și rotim $\implies 56$;
• $56 \cdot 2 = 112$, scoatem zerourile și rotim $\implies 211$;
• $211 \cdot 5 = 1055$, scoatem zerourile $\implies 155$; rotim $\implies 551$;

Exemplul 3

rotire25.in

2 42 1782321

rotire25.out

12

Explicație

Se rezolvă cerinţa $2$: $X = 42, K = 1782321$.
După ce se fac cele $K$ transformări se ajunge la numărul $12$.