În vistieria cetății se află N lacăte așezate în linie, numerotate de la 1 la N, fiecare având inscripționat un cod numeric în baza 10. Definim amprenta unui cod ca fiind un număr format din două cifre, \( \overline{XY} \) , unde \(X\) este cea mai mare cifră a codului, iar \(Y\) este cifra cea mai mică. De exemplu pentru codul 327003 amprenta este 70.

Două lacăte din șir situate pe pozițiile i și j formează o pereche echilibrată dacă i < j și codurile lor Cod[i] și Cod[j] au aceleași cifre, indiferent de ordinea și numărul de apariții al acestora. De exemplu, dacă primul lacăt din șir și al treilea au codurile Cod[1] = 1221 și Cod[3] = 211, atunci perechea (Cod[1], Cod[3]) este echilibrată deoarece ambele sunt formate exact din cifrele {1, 2} și 1 < 3.

Cerințe

Scrieți un program care rezolvă următoarele cerințe, cerința de rezolvat fiind dată de C ∈ {1, 2, 3}:

C=1. Determinați câte lacăte au amprenta formată din două cifre identice.
C=2. Considerăm că din fiecare cod trebuie să eliminăm exact o apariție a unei cifre, astfel încât suma amprentelor rezultate să fie maximă. Determinați această sumă.
C=3. Determinați numărul total de perechi echilibrate din șirul inițial al celor N lacăte.

Date de intrare

Fișierul de intrare lacate.in conține pe prima linie numărul C reprezentând cerința care trebuie rezolvată. Pe a doua linie, numărul N. Pe a treia linie, în ordine cele N coduri, numere naturale separate prin spații.

Date de ieșire

Fișierul de ieșire lacate.out va conține pe prima linie un singur număr reprezentând răspunsul la cerința rezolvată.

Restricții și precizări

• 1 ≤ N ≤ 50 000;
• 1 ≤ Codul oricărui lacăt din șir ≤ 100 000;
• Pentru C = 2, codul oricărui lacăt din șir ≥ 10.

Exemplul 1

lacate.in

1
8
132 213 34 334 4343 2 1223 666

lacate.out

2

Explicație

Amprentele lacătelor sunt 31 31 43 43 43 22 31 66 și avem 2 amprente cu cifre identice 22 și 66

Exemplul 2

lacate.in

2
8
132 213 34 334 4343 20 1223 666

lacate.out

314

Explicație

Codurile obținute după eliminarea câte unei cifre vor fi: 32 23 4 34 443 2 223 66, generând amprentele: 32 32 44 43 43 22 32 66, cu suma 314.

Exemplul 3

lacate.in

3
8
132 213 34 334 4343 2 1223 666

lacate.out

6

Explicație

Perechile echilibrate sunt (132, 213), (132,1223), (213, 1223), (34, 334), (34, 4343), (334,4343).