palindrom

Cu mult timp în urmă, într-un tărâm foarte, foarte îndepărtat, a existat o țară numită Tnamap. Locuitorii acestei țări puteau să aplice instantaneu transformări asupra cifrelor unui număr, utilizând un tablou de corespondențe $T$. O cifră $c$ a unui număr poate fi înlocuită cu cifra corespunzătoare ei, $T_c$.

Dalv şi Sogard, doi indivizi speciali ai acestei societăți ciudate se aflau în drum spre INO când au conștientizat că pot transforma instantaneu, folosind număr minim de transformări de cifre, orice număr $N$ într-un palindrom divizibil cu un număr natural $K$. Dacă sunt mai multe astfel de numere, îl determină pe cel mai mare.

Voi puteţi?

Cerință

Cunoscând valorile $T_0$, $T_1$, ..., $T_9$, numărul ce urmează a fi transformat $N$ și numărul $K$ (divizorul palindromului), determinați:

1. Numărul maxim care se poate obține aplicând transformări succesive numărului $N$ dat.
2. Cel mai mare dintre palindromurile divizibile cu $K$, ce se pot obține din numărul $N$, efectuând un număr minim de transformări asupra cifrelor numărului dat, respectiv asupra cifrelor numerelor obținute pe parcurs.

Date de intrare

Pe prima linie a fișierului de intrare palindrom.in sunt memorate 10 cifre distincte, separate prin câte un spațiu, reprezentând valorile $T_0$, $T_1$, ..., $T_9$.
Pe a doua linie sunt memorate cifrele numărului $N$.
Pe a treia linie este memorat numărul natural $K$.

Date de ieșire

Fișierul de ieșire palindrom.out va conține pe prima linie numărul maxim care se poate obține aplicând transformări succesive numărului $N$, iar pe a doua linie palindromul divizibil cu $K$, de valoare maximă, ce se poate obține din numărul $N$, efectuând un număr minim de transformări asupra cifrelor.

Restricții și precizări

• $1 \leq N \leq 10^{1\ 000\ 000}$
• $N$ are un număr par de cifre.
• $2 \leq K \leq 20$
• Se garantează faptul că toate testele au soluție.
• Pentru rezolvarea primei cerințe se va acorda $20\%$ din punctaj, iar pentru rezolvarea celei de-a doua cerințe se va acorda $80\%$ din punctaj.

Exemplu

palindrom.in

0 4 6 5 1 2 7 8 9 3
1234
3

palindrom.out

4994
4224

$\textcolor{red}{1}234 \rightarrow 4\textcolor{red}{2}34 \rightarrow 4\textcolor{red}{6}34 \rightarrow 4\textcolor{red}{7}34 \rightarrow 4\textcolor{red}{8}34 \rightarrow 4\textcolor{red}{9}34 \rightarrow 49\textcolor{red}{5}4 \rightarrow 49\textcolor{red}{2}4 \rightarrow 49\textcolor{red}{6}4 \rightarrow 49\textcolor{red}{7}4 \rightarrow 49\textcolor{red}{8}4 \rightarrow \textcolor{red}{4994}$

Numărul $N$ trece prin următoarele stări înainte de a deveni palindrom cu valoarea maximă, divizibil cu $3$: $\textcolor{red}{1}234 \rightarrow 42\textcolor{red}{3}4 \rightarrow 42\textcolor{red}{5}4 \rightarrow \textcolor{red}{4224}$