Firma MicroPhone, producător de aplicaţii software pentru telefoane mobile, dezvoltă programul de calcul tabelar MicroXL pentru a-l introduce în software-ul de bază al viitoarei generaţii de telefoane inteligente. În stadiul actual, aplicaţia permite lucrul pe o foaie de calcul compusă din N×N celule, în fiecare celulă putându-se introduce un număr natural nenul sau o formulă.
O formulă este precedată de semnul egal şi conţine un număr arbitrar, posibil zero, de operaţii de adunare. Termenii unei formule pot fi constante naturale nenule sau referinţe la alte celule, aşa cum se poate observa în figura de mai jos. Referinţa la o celulă se realizează specificând numărul liniei şi al coloanei corespunzătoare, separate prin caracterul “:”. Formula nu conţine spaţii.
Cerinţă
Scrieţi un program care determină valoarea fiecărei celule dintr-o foaie de calcul dată.
Date de intrare
Fişierul mxl.in conţine pe prima linie numerele naturale nenule N şi K, reprezentând numărul de linii şi coloane ale foii de calcul, respectiv numărul celulelor ce conţin date, iar pe următoarele K linii câte două numere întregi lin, col şi un şir de caractere s, cu semnificaţia: lin şi col reprezintă linia, respectiv coloana corespunzătoare unei celule, iar s este conţinutul celulei respective (număr natural nenul sau formulă).
Date de ieşire
Fişierul mxl.out va conţine N linii. Pe fiecare linie i se vor afla câte N numere naturale, separate prin câte un spaţiu, reprezentând valorile calculate pentru fiecare celulă de pe linia i a foii de calcul. Dacă o celulă nu conţine date sau formule se va afişa valoarea 0.
Restricţii
• 0 < N ≤ 40
• 0 < K ≤ N×N
• Constantele utilizate sunt numere naturale nenule mai mici sau egale cu 75
• Formulele au o lungime de cel mult 255 caractere şi pot fi calculate întotdeauna
• Nu există referinţe circulare
