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 NxM 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 Ai,j 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: Ai,j ≥ Ax,y – D (D fiind o constantă dată);
• pătratul (xf, yf) î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) Axf,yf≥Ax,y.
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), 1≤i≤N, 1≤j≤M.
Restricţii
• 1 ≤ N, M ≤ 800
• 0 ≤ D ≤ 100000
• 0 ≤ Ai,j ≤ 100000, 1≤i≤N, 1≤j≤M
• Destinaţia finală poate să coincidă cu punctul de plecare. Un drum format dintr-un singur pătrăţel este considerat valid.
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.