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ța

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

• 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ă.
• 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șierului de intrare balba.in 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 este 1, fișierul de ieșire balba.out 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ăr natural ce reprezintă câte numere diferite pot deveni X după o bâlbâială.

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

Restricții și precizări

• 1 ≤ N ≤ 100.000
• Numărul X este un număr natural nenul cu maximum 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 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 palilindromuri care se pot forma cu cifrele lui 24781487421, însă 87442112478 este cel mai mare dintre ele. Numărul 87442112478 este palilindrom, pentru ca 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 ca acesta se poate transforma după o bâlbâială într-un număr palindrom, și anume 44.