Problem 925: datorii

Într-o țară îndepărtată, economia este în criză. Cea mai mare problemă este lipsa de capital care creează blocaje financiare. De exemplu, o firmă $X$ poate avea datorii către o firmă $Y$ pe care nu le poate plăti, deoarece o altă firmă $Z$ are datorii către firma $X$ pe care nu le-a plătit, ș.a.m.d.

Există o listă cu toate datoriile firmelor sub forma următoare: $X > Y \ S$ , cu semnificația “firma $X$ datorează firmei $Y$ suma $S$ ”. Este posibil ca $X$ să aibă mai multe datorii la firma $Y$ (în funcție de contractele derulate împreună) sau chiar ca $X$ să aibă datorii la $Y$ și $Y$ să aibă datorii la $X$ .

Cerință

Cunoscând lista cu datoriile firmelor, scrieți un program care să rezolve următoarele cerințe:

Determină numărul de firme distincte care apar în această listă;
Realizează o situație financiară a firmelor distincte din această listă, scrise în ordine lexicografică; pentru fiecare firmă se vor determina două valori $SD \ SP$ , unde $SD$ reprezintă suma totală a datoriilor pe care firma le are către alte firme, iar $SP$ este totalul sumelor pe care firma trebuie să le primească de la alte firme.

Date de intrare

Fișierul de intrare datorii.in conține pe prima linie un număr natural $C$ reprezentând cerința care trebuie să fie rezolvată ( $1$ sau $2$ ). Pe a doua linie se află un număr natural $D$ care reprezintă numărul de înregistrări existente în lista datoriilor firmelor. Pe următoarele $D$ linii sunt descrise datoriile firmelor, în forma specificată în enunț, câte o datorie pe o linie.

Date de ieșire

Fișierul de ieșire datorii.out va conține răspunsul la cerința $C$ specificată în fișierul de intrare. Dacă $C = 1$ fișierul va conține un număr natural, reprezentând numărul de firme distincte care apar în lista menționată. Dacă $C = 2$ fișierul va conține pentru fiecare dintre firmele distincte din lista menționată câte un singur triplet de forma $X \ SD \ SP$ , unde $X$ este numele firmei, iar $SD$ și $SP$ au semnificația din enunț pentru firma $X$ ; tripletele vor fi scrise astfel încât numele firmelor să apară în ordine lexicografică, fiecare triplet pe câte o linie a fișierului, iar $X$ , $SD$ și $SP$ vor fi separate prin câte un singur spațiu.

Restricții și precizări

Există în total cel mult $6 \ 000$ de firme distincte în lista menționată de datorii.
Numele unei firme este format din maximum $20$ de caractere (litere mari și mici ale alfabetului englez, cifre, spații); se face distincție între literele mari și literele mici în numele firmelor; nu există alte restricții referitoare la numele firmelor.
Două firme distincte au nume distincte. O firmă nu poate avea datorii la ea însăși.
În descrierea unei datorii ( $X > Y \ S$ ) există un singur spațiu între $X$ și >, un singur spațiu între > și $Y$ , respectiv un singur spațiu între $Y$ și $S$ .
$1 \leq D \leq 80 \ 000$ ;
Sumele datorate de firme sunt numere naturale nenule $\leq 10^6$ ;
Dacă $X$ și $Y$ sunt numele a două firme distincte, iar $k$ ( $k \geq 0$ ) este valoarea maximă cu proprietatea că secvența formată din primele $k$ caractere din $X$ este identică cu secvența formată din primele caractere din $Y$ , spunem că $X$ precedă din punct de vedere lexicografic pe $Y$ dacă $X$ are doar $k$ caractere sau dacă al ( $k + 1$ )-lea caracter din $X$ este mai mic decât al ( $k + 1$ )-lea caracter din $Y$ .
Pentru teste valorând $30$ de puncte cerința este $1$ .
Pentru teste valorând $60$ de puncte cerința este $2$ .
Pentru teste valorând $40$ de puncte $D \leq 1 \ 000$ .
Pentru teste valorând $45$ de puncte numele firmelor nu conțin spații.

Exemplul 1

datorii.in

1
4
Vasile Inc > Anatolia 100
ana > Anatolia 10
ana > Vasilescu Inc 5
Popa25 PF > Anatolia 30

datorii.out

Exemplul 2