Problema Cufere

Alex, eroina din Minecraft, este foarte curajoasă și harnică. De-a lungul timpului, ea a depozitat în n cufere tot felul de obiecte fragile (de exemplu ouă) sau dure (de exemplu pietre). Un cufăr este o cutie de lemn cu 27 de compartimente dispuse pe 3 rânduri, câte 9 pe fiecare rând. Într-un compartiment poate fi depozitat un grup de unul sau mai multe obiecte identice: maximum 16 obiecte fragile sau maximum 64 de obiecte dure. Pot fi mai multe compartimente care să conțină același tip de obiecte, iar unele compartimente pot fi goale.

Alex a etichetat atât compartimentele, cât și obiectele, cu numere construite după următoarea regulă:

• un obiect are drept etichetă un număr natural cuprins între 10 și 99, inclusiv, astfel: un număr prim, dacă este fragil, sau un număr compus, dacă este dur;
• toate obiectele identice primesc aceeași etichetă;
• un compartiment are drept etichetă un număr natural format din două valori alipite: numărul obiectelor din grupul depozitat în el, urmat de eticheta comună a acestora (de exemplu dacă eticheta compartimentului este 1994, înseamnă că în el este depozitat un grup de 19 obiecte, fiecare având eticheta 94);
• compartimentele goale sunt etichetate cu 0.

Alex vrea să rearanjeze obiectele din cufere, astfel încât:

• să fie valorificat spațiul, adică să fie ocupate cât mai puține cufere și, în cadrul unui cufăr, cât mai puține compartimente;
• să fie ocupate compartimentele din cuferele disponibile la rând, începând cu primul cufăr, și, în cadrul unui cufăr, începând cu primul rând și, în cadrul unui rând, de la stânga la dreapta. Cu alte cuvinte, se umple mai întâi cufărul 1, începând cu rândul 1, și pe fiecare rând de la stânga la dreapta, apoi cufărul al doilea, în aceeași manieră, și așa mai departe;
• obiectele sunt preluate în ordinea crescătoare a etichetelor și din totalul obiectelor identice se formează mai întâi grupuri cu număr maxim de obiecte, și doar ultimul grup poate fi, eventual, incomplet;
• fiecare din aceste grupuri se depozitează, pe măsura formării, în câte un compartiment al cufărului curent, iar dacă acesta se umple, se trece la cufărul următor.

După rearanjarea obiectelor, compartimentele sunt etichetate din nou, după aceeași regulă.

Cerință

Dându-se cele n cufere, care conțin obiectele în ordinea inițială, Alex vă roagă să realizați un program care să determine:

• pentru fiecare etichetă distinctă de obiect întâlnit în cele n cufere, numărul total al obiectelor cu acea etichetă;
• noile etichete ale compartimentelor care compun cele n cufere, după rearanjarea obiectelor.

Date de intrare

Fișierul de intrare cufere.in conține pe prima linie numărul c reprezentând cerința care trebuie să fie rezolvată (1 sau 2), pe a doua linie numărul natural nenul n, cu semnificația din enunț, iar pe fiecare din următoarele 3n linii, câte 9 numere, reprezentând etichetele inițiale ale compartimentelor aflate pe câte un rând al unui cufăr, în ordinea în care ele se află în cufere, de la primul cufăr, până la ultimul, în cadrul fiecărui cufăr de la primul rând până la al treilea, iar în cadrul fiecărui rând de la stânga la dreapta. Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire cufere.out va conține fie răspunsul pentru cerința 1 (dacă c = 1), fie răspunsul pentru cerința 2 (dacă c = 2).

Pentru cerința 1, pentru fiecare etichetă distinctă, în ordine strict crescătoare, se va afișa o pereche formată din eticheta respectivă și numărul obiectelor cu această etichetă. Fiecare pereche de numere va fi afișată pe câte o linie.

Pentru cerința 2, etichetele compartimentelor vor fi afișate corespunzător plasării lor în cufere, câte 9 pe fiecare linie a fișierului, de la primul cufăr până la ultimul, în cadrul fiecărui cufăr de la primul rând până la al treilea, iar în cadrul fiecărui rând de la stânga la dreapta.

Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu.

Restricții și precizări

• c ∈ {1, 2}
• 1 ≤ n ≤ 10.000
• Eticheta unui obiect este cuprinsă între 10 și 99 inclusiv
• În cazul cerinței 2, se vor afișa etichetele pentru toate compartimentele, chiar dacă ele sunt goale sau provin din cufere complet goale.

Exemple