Problem 783: placare

O suprafaţă dreptunghiulară de înălţime $N$ şi lăţime $M$ unităţi trebuie acoperită perfect (placată) prin utilizarea unor plăci de formă dreptunghiulară de dimensiune $1 \times P$ sau $P \times 1$ , unde $P$ este un număr natural nenul. Suprafaţa dată poate fi privită ca un caroiaj cu $N \times M$ pătrăţele egale cu unitatea.

O placare corectă a suprafeţei iniţiale se memorează într-un fişier text folosind următoarele convenţii de codificare:

Pe prima linie se precizează dimensiunile $N$ şi $M$ ale suprafeţei;
O placă dreptunghiulară de laţime $P$ este codificată prin numărul natural $P$ , iar o placă de înalţime $P$ se codifică prin numărul întreg $–P$ ;
Convenim că placa având ambele dimensiuni egale cu unitatea să se codifice cu valoarea $1$ ;
Pe fiecare din cele $N$ linii ale codificării se află câte un şir de valori întregi reprezentând, în ordine de la stânga la dreapta, codurile plăcilor care se găsesc amplasate începând de la respectiva linie;
Codul $P$ strict mai mare ca $1$ al unei plăci orizontale apare o singură dată pe linia corespunzătoare pe care se află placa, iar codul $–P$ al unei plăci verticale va apare o singură dată şi anume pe prima linie de la care placa respectivă este amplasată în jos pe o anumită coloană a suprafeţei;
Dacă pe o anumită linie a suprafeţei nu există astfel de coduri de plăci, atunci pe respectiva linie din fişier este o singură valoare de $0$ .

Folosind codificarea unei placări a suprafeţei iniţiale, se poate determina imaginea acestei placări sub forma unui tablou bidimensional $A$ , cu $N$ linii şi $M$ coloane, unde $A_{i,j}$ reprezintă valoarea absolută a codului plăcii care se suprapune peste pătrăţelul de pe linia $i$ şi coloana $j$ .

Cerinţă

Cunoscând codificarea unei placări corecte a suprafeţei date să se obţină imaginea acestei placări (matricea de valori corespunzătoare codificării suprafeţei).

Date de intrare

Fişierul de intrare placare.in are următoarea structură:

pe prima linie valorile naturale $N$ și $M$ , separate printr-un spaţiu, unde $N$ este înălţimea suprafeţei și $M$ este lăţimea suprafeţei.
pe fiecare din următoarele $N$ linii se află un şir de valori întregi, separate prin câte un spaţiu, reprezentând codificarea respectivei linii a placării.

Date de ieşire

În fişierul de ieşire placare.out se va tipări tabloul bidimensional ce reprezintă imaginea placării, compus din $N$ linii, pe fiecare dintre ele aflându-se $M$ valori naturale separate prin câte un spaţiu, cu semnificaţia din enunţ.

Restricţii şi precizări

$1 \leq N,M \leq 300$
Pentru $80\%$ din teste, $1 \leq N,M \leq 100$ ;
Dimensiunea $P$ sau $–P$ a unei plăci este aleasă astfel încât acoperirea obţinută să nu depăşească înălţimea $N$ sau lățimea $M$ a suprafeţei.
Datele din fişierul de intrare sunt corecte în sensul că reprezintă codificarea unei acoperiri a zonei dreptunghiulare de dimensiuni $N$ şi $M$ .

Exemplul 1

placare.in

placare.out

Explicație

Valoarea $-4$ codifică o placă de înălţime $4$ şi lăţime $1$ plasată începând din pătratul de coordonate $(1,1)$ şi până în pătratul de coordonate $(4,1)$ .
Valoarea $3$ de pe ultima linie a codificării desemnează o placă de lăţime $3$ şi înălţime $1$ , plasată orizontal, începând din pătrăţelul de coordonate $(4,2)$ .

Exemplul 2