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, Tc.
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 T0, T1, …, T9, 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 palindrom1.in sunt memorate 10 cifre distincte, separate prin câte un spaţiu, reprezentând valorile T0, T1, …, T9.
Pe a doua linie sunt memorate cifrele numărului N, iar pe cea de a treia linie un numărul natural K.
Date de ieşire
Fişierul palindrom1.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
• 1≤N<101.000.000
• N are un număr par de cifre
• 2 ≤ K ≤ 20
• Se garantează faptul că toate testele au soluţie.
Exemple
palindrom1.in
palindrom1.out
Explicaţii
0 4 6 5 1 2 7 8 9 3
1234
3
4994
4224
1234-4234-4634-4734-4834-4934-4954-4924-4964-4974-4984-4994
Numărul N trece prin următoarele stări înainte de a deveni palindrom cu valoarea maximă, divizibil cu 3:
1234-4234-4254-4224.
