MXL

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 \cdot 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 și precizări

• $0 < N ≤ 40$
• $0 < K ≤ N \cdot 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

Exemplu

mxl.in

5 7
1 1 =1:2+5
1 2 =1:3+4
1 3 =3+1:4
1 4 =1:5+2
1 5 1
4 3 =1+2+3
3 1 =13

mxl.out

15 10 6 3 1 
0 0 0 0 0 
13 0 0 0 0 
0 0 6 0 0 
0 0 0 0 0