Zachody Słońca
Limit pamięci: 64 MB
Mieszkańcy Bajtogrodu uwielbiają oglądać zachody Słońca z dachów swoich
domów mieszkalnych.
Jeśli zachód jest wyjątkowo spektakularny, niektórzy wybierają się nawet na dachy pobliskich
budynków, jeśli mogą mieć stamtąd lepszy widok.
Miasto jest rozmieszczone na planie kraty o boku długości , budynki znajdują się w punktach kratowych.
Odległość między dwoma punktami wyraża się przez metrykę miejską.
Jan zamierza kupić nowe mieszkanie. Jest on wielkim miłośnikiem zachodów Słońca i jest gotów
chodzić do budynków położonych nie dalej niż jednostek od swojego lokum.
Pomóż Janowi podjąć trudną decyzję o wyborze lokalizacji mieszkania.
Mając dany plan Bajtogrodu z podanymi wysokościami budynków utwórz nowy plan,
w którym przy każdym budynku będzie podana wysokość najwyższego wieżowca,
do którego może dotrzeć Jan jeśli w tym budynku zamieszka.
Zadanie
Napisz program, który:
- wczyta ze standardowego wejścia plan miasta z podanymi wysokościami budynków,
- wypisze na standardowe wyjście zmodyfikowany plan miasta, w którym w każdym punkcie kratowym znajdzie się wysokość
najwyższego budynku, oddalonego od tego punktu co najwyżej o jednostek w metryce miejskiej.
Dla przypomnienia, odległość miejska dwóch punktów
i
to
Wejście
W pierwszym wierszu wejścia znajdują się dwie liczby naturalne oraz (, ),
oddzielone pojedynczym odstępem.
W każdym z kolejnych wierszy znajduje się nieujemnych liczb całkowitych, pooddzielanych pojedynczymi
odstępami i niewiększych niż - opisują one plan Bajtogrodu.
Wyjście
W każdym z wierszy wyjścia powinno się znaleźć liczb całkowitych nieujemnych, pooddzielanych pojedynczymi
odstępami i opisujących zmodyfikowany plan Bajtogrodu.
Przykład
Dla danych wejściowych:
4 2
1 3 4 5
0 2 2 3
4 1 1 3
6 2 3 0
poprawną odpowiedzią jest:
4 5 5 5
6 4 5 5
6 6 4 5
6 6 6 3
Autor zadania: Krzysztof Dulęba.