Zachody Słońca 2
Limit pamięci: 96 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 kwadratu o boku , 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 opis planu miasta,
- obliczy 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
i wypisze sumę tych wartości modulo .
Dla przypomnienia, odległość miejska dwóch punktów
i
to
Wejście
W pierwszym wierszu wejścia znajdują się trzy liczby naturalne , oraz
(, , ), pooddzielane pojedynczymi odstępami.
służy do wygenerowania planu miasta. Budynek stojący w wierszu i kolumnie ma wysokość
.
Wyjście
W jedynym wierszu wyjścia ma się znaleźć jedna liczba naturalna: suma (po wszystkich domach)
wysokości najwyższych budynków leżących w odległości co najwyżej , modulo .
Przykład
Dla danych wejściowych:
4 2 1
poprawną odpowiedzią jest:
1836
Autor zadania: Krzysztof Dulęba.