Institut

Un institut de istorie colectează obiecte descoperite pe mai multe șantiere arheologice. Pentru fiecare descoperire de pe șantier se stabilește categoria din care face parte obiectul (de exemplu: ceramică, monedă etc.), materialul din care este confecționat și numărul de exemplare ce fac parte din aceeași categorie și au același material. Categoria și materialul unui obiect sunt reprezentate prin numere naturale nenule.

Pentru fiecare șantier se cunoaște: numărul total de valori transmise institutului, grupate în șiruri formate din $2$ sau $3$ numere naturale nenule ce sunt urmate de un număr negativ (ce marchează sfârșitul unui șir), fiecare asemenea șir codifică datele unei descoperiri. Primul număr dintr-un șir reprezintă categoria din care face parte obiectul descoperit, al doilea număr reprezintă materialul din care este confecționat obiectul, al treilea număr indică numărul de exemplare, descoperite la acea operație. Dacă șirul are numai $2$ numere pozitive, atunci s-a descoperit un singur exemplar din acel obiect. De exemplu, șirul de numere $3$, $7$, $4$, $-2$ va reprezenta o descoperire a $4$ exemplare din categoria $3$, confecționate din materialul $7$ (categoria $3$ poate fi monezi, materialul $7$ poate fi bronz și sunt $4$ exemplare descoperite: deci s-au descoperit $4$ monezi din bronz).

Cerință

Scrieţi un program care determină și afișează pentru datele trimise de $n$ șantiere către institut:

1. Lista obiectelor în ordine crescătoare după categorie: se va afișa categoria și numărul total de exemplare descoperite pe toate șantierele la acea categorie.
2. Lista obiectelor descoperite în ordine crescătoare după categorie: pentru fiecare obiect se afișează categoria, materialul și numărul de exemplare descoperite, ce au aceste caracteristici.

Date de intrare

Fișierul de intrare institut.in conține pe prima linie două numere naturale $c$ și $n$: $c$ reprezintă cerința și are una din valorile $1$ sau $2$ și $n$ reprezintă numărul de șantiere arheologice.

Fiecare dintre următoarele $n$ linii din fișier conține un șir de numere întregi, separate prin spațiu, ce reprezintă datele trimise de un șantier, în ordinea următoare: numărul total de valori, șiruri formate din $2$ sau $3$ numere naturale nenule urmate de un număr negativ, ce codifică pentru descoperirea făcută: categoria, materialul și numărul de exemplare cu aceste caracteristici pentru obiectele descoperite.

Date de ieșire

Fișierul de ieșire institut.out va conține:

1. Dacă $c = 1$, fișierul de ieșire institut.out va conține pe fiecare linie două numere naturale, separate printr-un spațiu, ce reprezintă categoria și numărul total de exemplare descoperite la acea categorie, pe toate șantierele, în ordinea crescătoare a categoriilor.
2. Dacă $c = 2$, fișierul de ieșire institut.out va conține pe prima linie un număr natural $d$ ce reprezintă numărul total de descoperiri de pe toate șantierele și pe fiecare dintre următoarele $d$ linii câte trei numere naturale, separate prin spațiu, ce reprezintă în această ordine: categoria obiectului descoperit, materialul obiectului și numărul de exemplare descoperite. Cele $d$ linii vor fi afișate în ordinea crescătoare a categoriilor obiectelor și pentru obiecte cu aceeași categorie, în ordinea crescătoare a materialului.

Restricții și precizări

• $4 \leq n \leq 400$;
• Categoria, materialul și numărul de exemplare ale unui obiect sunt numere naturale nenule cu cel mult $2$ cifre.
• Numărul total de valori transmise de un șantier institutului este cel mult $600$;
• Numărul de descoperiri de pe toate șantierele este cel mult $10 \ 000$.
• Pentru datele de test, se consideră că obiectele oricăror două descoperiri diferite nu au aceeași categorie și același material.
• Pentru rezolvarea cerinței $1$ se obțin maxim $40$ de puncte, pentru cerința $2$ se obțin maxim $50$ de puncte.

Exemplul 1

institut.in

1 4  
10 1 6 -5 7 2 -8 2 10 3 -4 
10 2 5 -7 2 6 2 -4 1 5 -7 
6 3 8 -6 7 5 -1  
4 2 1 5 -6

institut.out

1 2 
2 11 
3 1 
7 2

Explicație

Sunt $4$ șantiere arheologice, pentru fiecare se cunoaște numărul de valori trimise: pentru primul șantier sunt $10$ valori, cu șirurile următoare ce reprezintă descoperiri efectuate:

• șirul $(1,6,-5)$ reprezintă categoria $1$, materialul $6$, $1$ exemplar;
• șirul $(7,2, -8)$ reprezintă categoria $7$, materialul $2$, $1$ exemplar;
• șirul $(2,10,3,-4)$ reprezintă categoria $2$, materialul $10$, $3$ exemplare etc.

Se afișează pe categorii, obiectele descoperite de pe toate șantierele, în ordinea crescătoare a categoriilor:

• sunt $2$ exemplare la categoria $1$,
• $11$ exemplare la categoria $2$: $(2,10,3, -4)$, $(2,5,-7)$, $(2,6,2,-4)$, $(2,1,5,-6)$,
• $1$ exemplar la categoria $3$
• $2$ exemplare la categoria $7$.

Exemplul 2

institut.in

2 4  
10 1 6 -5 7 2 -8 2 10 3 -4 
10 2 5 -7 2 6 2 -4 1 5 -7 
6 3 8 -6 7 5 -1  
4 2 1 7 -6

institut.out

9 
1 5 1 
1 6 1 
2 1 7 
2 5 1 
2 6 2 
2 10 3 
3 8 1 
7 2 1 
7 5 1

Explicație

Sunt $9$ descoperiri de obiecte, ce sunt afișate pe categorii în sens crescător: la aceeași categorie, se afișează după material, în sens crescator.