Rezolvare PBinfo #4376

Legenda spune că există o Matrice cu N linii (numerotate de la 1 la N) şi M coloane (numerotate de la 1 la M). O celulă va fi identificată prin linia şi coloana pe care se află. Această Matrice mistică are inițial în toate celulele valoarea 0.

Asupra Matricei poţi efectua Q transformări. La o transformare, atingi o celulă (i,j), iar Matricea te va întreba (da, Legenda spune că Matricea vorbește): “Ce valoare vrei să aduni, maestre?”. Dacă tu răspunzi x, atunci Matricea mistică va construi un triunghi dreptunghic isoscel cu unghiul drept în celula (i,j), celelalte colţuri fiind în celulele (i-x+1, j), respectiv (i,j-x+1). Dacă triunghiul nu încape integral în Matrice, Matricea va ignora cerința ta. În caz contrar, în celula (i,j) Matricea va aduna valoarea x, iar la celelalte celule din triunghi se va aduna o valoare cu 1 mai mică decât valoarea adunată la celula din triunghi situată sub ea sau în dreapta ei.

De exemplu, dacă prima dată tu ai atins celula (5,6), iar la întrebarea Matricii tu ai răspuns 4, Matricea va aduna numere după cum se observă în figură:

Cerința

Date fiind N, M, Q reprezentând numărul de linii, numărul de coloane, respectiv numărul de transformări, precum şi cele Q transformări efectuate, să se determine Matricea după efectuarea celor Q transformări.

Date de intrare

Fișierul de intrare legenda.in conține pe prima linie numerele naturale N, M și Q. Pe fiecare dintre următoarele Q linii se va afla câte o transformare sub forma a trei numere naturale i j x, unde i și j reprezintă linia, respectiv coloana pe care se află celula atinsă, iar x reprezintă valoarea spusă la întrebarea Matricii. Valorile scrise pe aceeaşi linie vor fi separate prin câte un spaţiu.

Date de ieșire

Fișierul de ieșire legenda.out va conţine N linii, pe fiecare linie fiind scrise câte M numere naturale separate prin câte un spaţiu reprezentând Matricea după efectuarea celor Q transformări.

Restricții și precizări

• 1 ≤ N, M ≤ 1000
• 1 ≤ Q ≤ 4000
• Răspunsurile la întrebarea Matricei sunt numere naturale nenule cu maximum 8 cifre.
• Aceeași celulă poate fi atinsă de mai multe ori.

Exemplu:

legenda.in

7 10 4
5 6 4
2 2 5
5 8 5
7 8 2

legenda.out

0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 1 1 2 0 0
0 0 0 0 1 3 2 3 0 0
0 0 0 1 3 5 3 4 0 0
0 0 1 3 5 7 4 5 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 2 0 0