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 .

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.