Palindrom

Matei este fascinat de numere. La școală a auzit de număr palindrom ca fiind acel număr care citit de la stânga la dreapta este identic cu numărul citit de la dreapta la stânga. El a observat că, pentru anumite numere, rearanjând toate cifrele numărului, se poate obține un număr palindrom. De exemplu, pentru numărul $123213$ se pot forma următoarele palindromuri: $231132$, $312213$, $321123$, $213312$, $123321$, $132231$. Dintre toate aceste palindromuri, el îl alege pe cel mai mic, și-l numeste palindrom mic asociat.
Pentru numărul $123212$ nu se poate forma niciun număr palindrom. În acest caz, Matei vrea să afle numărul minim de modificări pe care le poate efectua asupra numărului, astfel încât din cifrele lui să se poată construi un palindrom. Prin modificare se înțelege înlocuirea unei cifre cu o altă cifră. Pentru $\textbf{123212}$, este suficientă o singură modificare: fie se înlocuiește cifra $\textbf{3}$ cu cifra $\textbf{2}$, fie una dintre cifrele $\textbf{2}$ cu cifra $\textbf{3}$.

Cerință

Scrieți un program care, pentru un șir de $N$ numere naturale, să afișeze:

1. Pentru fiecare număr din șir, cel mai mic palindrom asociat care se poate construi din toate cifrele sale sau $\textbf{-1}$, dacă acest lucru nu este posibil.
2. Numărul de grupe maximale de numere alăturate din șir, în care niciun număr nu are palindrom asociat.
3. Numărul total minim de modificări necesare, astfel încât toate numerele din șir să aibă un număr palindrom asociat.

Date de intrare

Fişierul de intrare palindrom.in conține:

• pe prima linie un număr natural $C$, reprezentând cerința care trebuie rezolvată ($1$, $2$ sau $3$);
• pe a doua linie $N$, având semnificația din enunț;
• pe a treia linie $N$ numere naturale, separate prin câte un spațiu, cu semnificația din enunț.

Date de ieșire

Fişierul de ieşire palindrom.out conţine:

1. Pentru $C=1$: $N$ numere separate printr-un spațiu, având semnificația din enunț;
2. Pentru $C=2$: un număr natural reprezentând numărul de grupe maximale cu proprietatea cerută;
3. Pentru $C=3$: un număr natural reprezentând numărul total minim de modificări necesare pentru ca toate numerele din șir să aibă un palindrom asociat.

Restricții și precizări

• $1 \leq N \leq 1 \ 000$
• Numerele din șir sunt $\leq 1 \ 000 \ 000 \ 000$
• O grupă maximală este o secvență de numere aflate pe poziţii consecutive în şirul dat, care nu mai poate fi extinsă nici la stânga, nici la dreapta prin adăugarea unui număr cu aceeași proprietate;
• Pentru rezolvarea corectă a cerinţei $\textbf{1}$ se acordă 40% din punctaj, pentru rezolvarea corectă a cerinţei $\textbf{2}$ se acordă 30% din punctaj, iar pentru rezolvarea corectă a cerinței $\textbf{3}$ se acorda 30% din punctaj.

Exemplul 1

palindrom.in

1
7
334422 1234 1003341 33009 5857 121298 911

palindrom.out

234432 -1 1034301 30903 -1 -1 191

Exemplul 2

palindrom.in

2
7
334422 1234 1003341 33009 5857 121298 911

palindrom.out

2

Explicație

Numerele fără palindrom asociat sunt $1234$, $5857$ și $121298$. Ele apar în șir în două grupuri de numere alăturate: $[1234]$ și $[5857, 121298]$.

Exemplul 3

palindrom.in

3
7
334422 1234 1003341 33009 5857 121298 911

palindrom.out

4

Explicație

Numerele care nu au palindrom asociat:

• $1234$ – sunt necesare $2$ modificari (de exemplu cifra $1$ se modifică în cifra $2$ și cifra $3$ în cifra $4$);
• $5857$ - este necesară o singură modificare (de exemplu cifra $8$ se modifică în cifra $7$);
• $121298$ – este necesară o singură modificare (modificăm cifra $8$ în cifra $9$).

Numărul total de modificări este $2+1+1=4$