balba

Regele George al VI-lea al Regatului Unit s-a confruntat cu o problemă neobișnuită pentru o persoană care trebuia să țină discursuri: era bâlbâit. Acesta se bâlbâia chiar și când spunea numere. Interesant este faptul că, atunci când spunea un număr, el repeta doar una dintre cifrele acelui număr, imediat după ce pronunța cifra respectivă.

Spre exemplu, numărul $70243$ putea fi rostit atunci când se bâlbâia ca $770243$ sau ca $700243$ sau ca $702243$ sau ca $702443$ sau ca $702433$.

Un palilindrom este un număr natural pentru care există o bâlbâială a regelui care îl transformă într-un palindrom.

Spre exemplu, $25373552$ este un palilindrom, pentru că după o bâlbâială poate deveni $255373552$, acesta fiind un număr palindrom.

Cerințe

Fiind dat un număr natural nenul $X$, să se determine:

1. Câte numere diferite poate genera $X$ după o bâlbâială și câte numere diferite pot deveni $X$ după o bâlbâială.
2. Cel mai mare număr palilindrom care se poate forma cu cifrele lui $X$. Nu este obligatoriu să se folosească toate cifrele lui $X$.

Date de intrare

Pe prima linie a fișierul de intrare se află numărul $C$, număr care poate fi $1$ sau $2$ și reprezintă cerința ce trebuie rezolvată.
Pe cea de-a doua linie se află numărul $N$, reprezentând numărul de cifre al numărului $X$.
Pe următoarea linie se află, în ordine, cifrele lui $X$, separate prin câte un spațiu.

Date de ieșire

Dacă $C = 1$, fișierul de ieșire va avea obligatoriu două linii, fiecare linie conținând exact un număr.

Pe prima linie se va scrie un număr natural ce reprezintă câte numere diferite poate genera $X$ după o bâlbâială.
Pe cea de-a doua linie se va scrie un numărul natural ce reprezintă câte numere diferite pot deveni $X$ după o bâlbâială.

Dacă $C = 2$, pe prima linie a fișierul de ieșire se va scrie cel mai mare număr palilindrom ce se poate crea cu cifrele lui $X$.

Restricții și precizări

• $1 \leq N \leq 10^5$
• Numărul $X$ este un număr natural nenul cu maxim $100\ 000$ de cifre.
• Un număr palindrom este un număr care are aceeași valoare dacă este citit de la stânga la dreapta sau de la dreapta la stânga.
• Pentru rezolvarea corectă a cerinței 1 se vor acorda 40 de puncte. Pentru fiecare număr corect afișat se va acorda jumătate din punctajul asociat testului.
• Pentru rezolvarea corectă a cerinței 2 se vor acorda 60 de puncte.

Exemplul 1

balba.in

1
8
7 0 2 2 4 3 3 3

balba.out

5
2

Explicație

Numerele diferite care pot fi generate din $70224333$ printr-o bâlbâială sunt: $770224333$, $700224333$, $702224333$, $702244333$, $702243333$.
Numerele diferite din care $70224333$ poate fi generat printr-o bâlbâială sunt: $7024333$, $7022433$.

Exemplul 2

balba.in

1
25
1 2 3 1 2 3 4 1 2 3 4 5 1 2 3 4 5 6 1 2 3 4 5 6 7

balba.out

25
0

Explicație

Sunt 25 de numere diferite care pot fi generate din $X$ printr-o bâlbâială, însă $X$ nu
poate fi generat de niciun număr printr-o bâlbâială.

Exemplul 3

balba.in

2
11
2 4 7 8 1 4 8 7 4 2 1

balba.out

87442112478

Explicație

Mai există și alte palilindroame care se pot forma cu cifrele lui $24781487421$, însă
$87442112478$ este cel mai mare dintre ele. Numărul $87442112478$ este palilindrom, pentru că acesta se poate transforma după o bâlbâială într-un număr palindrom, și anume $874421124478$.

Exemplul 4

balba.in

2
7
1 2 3 4 0 0 0

balba.out

4

Explicație

Nu se poate forma un palilindrom care să aibă toate cifrele lui $X$. Astfel, cel mai mare palilindrom care se poate crea folosind cifrele lui $X$ este $4$. Numărul $4$ este palilindrom, pentru că acesta se poate transforma după o bâlbâială într-un număr palindrom, și anume $44$.