h2. Date de intrare

Fisierul de intrare $mexc.in$ contine pe prima linie trei numere naturale $N$ $M$ $D$ , separate prin cate un spatiu, cu semnificatia din enunt. Fiecare dintre urmatoarele $N$ linii vor conţine cate $M$ numere naturale, separate prin cate un spatiu, reprezentand valorile elementelor matricei A.

Fisierul de intrare $mexc.in$ contine pe prima linie trei numere naturale $N$ $M$ $D$ , separate prin cate un spatiu, cu semnificatia din enunt. Fiecare dintre urmatoarele $N$ linii vor conţine cate $M$ numere naturale, separate prin cate un spatiu, reprezentand valorile elementelor matricei A.

h2. Date de iesire

Fisierul de iesire $mexc.out$ va contine $N$ linii pe care se vor scrie câte $M$ numere naturale, separate prin cate un spatiu, numarul i de pe linia j din fisier reprezentand numarul de destinatii finale distincte care pot fi atinse pe drumuri valide ce pornesc din pătratul (i,j), ∀ 1≤i≤N, 1≤j≤M.
 

Fisierul de iesire $mexc.out$ va contine $N$ linii pe care se vor scrie câte $M$ numere naturale, separate prin cate un spatiu, numarul i de pe linia j din fisier reprezentand numarul de destinatii finale distincte care pot fi atinse pe drumuri valide ce pornesc din patratul (i,j), ∀ $1 ≤ i ≤ N $ , $1 ≤ j ≤ M$

h2. Restrictii

* $... ≤ ... ≤ ...$

* $1 ≤ $N$ , $M$ ≤ 800$
* $0 ≤ $D$ ≤ 100000 $
* $0 ≤ $A(i,j) ≤ 100000 $ , ∀ $1 ≤ i ≤ N $ , $1 ≤ j ≤ M$
* Destinatia finala poate sa coincida cu punctul de plecare. Un drum format dintr-un singur patratel este considerat valid.
 

h2. Exemplu
table(example). |_. mexc.in |_. mexc.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 5 6 2
  7 7 7 7 7 7
  7 3 3 3 3 7
  7 3 5 6 3 7
  7 3 3 3 3 7
  7 7 7 7 7 10
| 18 18 18 18 18 18
  18 30 30 30 30 18
  18 30 20 1 30 18
  18 30 30 30 30 18
  18 18 18 18 18 1

|
h3. Explicatie

...

Pentru patratelele de înaltime $7$ destinatia finala poate fi orice patratel de inaltime $7$ si patratelul de inaltime $10$.
Pentru patratelele de înaltime $3$ destinatia finala poate fi orice patratel.
Pentru patratelul de înaltime $5$ destinatia finala poate fi orice patratel mai putin cele de inaltime $3$.
Pentru patratelul de înaltime $6$ destinatia finala poate fi doar el însusi (nu poate trece prin patratelele de inaltime $3$ datorita primei restrictii)
Pentru patratelul de înaltime $10$ destinatia finala poate fi doar el insusi.
 

== include(page="template/taskfooter" task_id="mexc") ==