mexc

Proaspăt scăpat de conflictele sale cu poliţia, Gigel vrea să organizeze o excursie la munte. El a descoperit o suprafaţă dreptunghiulară de $N$ metri lăţime şi $M$ metri lungime, împărţită în $N \cdot M$ suprafeţe pătratice elementare de latură $1$ şi cu laturile paralele cu laturile suprafeţei. Pentru simplitate, ne vom referi la ea ca la o matrice notată cu $A$ având $N$ linii (numerotate de la $1$ la $N$) şi $M$ coloane (numerotate de la $1$ la $M$). Pentru fiecare pătrat $(i, j)$ se cunoaşte înălţimea $A_{ij}$ la care acesta se află.

Dintr-un pătrat $(i, j)$, Gigel se poate deplasa, în interiorul suprafeţei, în oricare din pătratele: $(i, j+1)$, $(i, j-1)$, $(i-1, j)$, $(i+1, j)$, în cazul în care acestea există. Un drum valid în viziunea lui Gigel este un drum care pleacă din orice pătrat $(x, y)$ şi are proprietăţile:

• înălţimea fiecărui pătrat $(i, j)$ prin care trece, satisface relaţia: $A_{ij} \geq A_{xy} - D$ ($D$ fiind o constantă dată);
• pătratul $(x_f, y_f)$ în care drumul se termină (denumit destinaţie finală), are înălţimea mai mare sau egală cu înălţimea pătratului $(x, y) \ A_{x_f \ y_f} \geq A_{xy}$.

Cerinţă

Să se scrie un program care să-l ajute pe Gigel să afle, pentru fiecare pătrat iniţial, câte destinaţii finale distincte există pentru drumurile valide care pornesc din acel pătrat.

Date de intrare

Fişierul de intrare mexc.in conţine pe prima linie trei numere naturale $N \ M \ D$, separate prin câte un spaţiu, cu semnificaţia din enunţ. Fiecare dintre următoarele $N$ linii vor conţine câte $M$ numere naturale, separate prin câte un spaţiu, reprezentând valorile elementelor matricei $A$.

Date de ieșire

Fişierul de ieşire mexc.out va conţine $N$ linii pe care se vor scrie câte $M$ numere naturale, separate prin câte un spaţiu, numărul $i$ de pe linia $j$ din fişierul mexc.out reprezentând numărul de destinaţii finale distincte care pot fi atinse pe drumuri valide ce pornesc din pătratul $(i, j)$.

Restricții și precizări

• $1 \leq N, M \leq 800$
• $0 \leq D \leq 100 \ 000$
• $0 \leq A_{ij} \leq 100 \ 000$
• Destinaţia finală poate să coincidă cu punctul de plecare. Un drum format dintr-un singur pătrăţel este considerat valid.

Exemplu

mexc.in

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

mexc.out

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

Explicație

Pentru pătrăţelele de înălţime $7$ destinaţia finală poate fi orice pătrăţel de înălţime $7$ şi pătrăţelul de înălţime $10$.
Pentru pătrăţelele de înălţime $3$ destinaţia finală poate fi orice pătrăţel.
Pentru pătrăţelul de înălţime $5$ destinaţia finală poate fi orice pătrăţel mai puţin cele de înălţime $3$.
Pentru pătrăţelul de înălţime $6$ destinaţia finală poate fi doar el însuşi (nu poate trece prin pătrăţelele de înălţime $3$ datorită primei restricţii)
Pentru pătrăţelul de înălţime $10$ destinaţia finală poate fi doar el însuşi.