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.</p>

Miasto jest rozmieszczone na planie kwadratu o boku n, 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ż k 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 k jednostek w metryce miejskiej i wypisze sumę tych wartości modulo 2²⁸.

Dla przypomnienia, odległość miejska dwóch punktów (a_x, a_y) i (b_x, b_y) to

p((a_x,a_y),(b_x,b_y)) = |a_x - b_x| + |a_y - b_y|

입력 형식

W pierwszym wierszu wejścia znajdują się trzy liczby naturalne n, k oraz seed(1 ≤ n ≤ 3000, 1 ≤ k ≤ 1000, 1 ≤ seed ≤ 1000), pooddzielane pojedynczymi odstępami. seed służy do wygenerowania planu miasta. Budynek stojący w wierszu i i kolumnie j ma wysokość (3ⁱ + 5ⁱ · seed)mod2²⁸.</p>

출력 형식

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 k, modulo 2²⁸.</p>

예제 입력

4 2 1

예제 출력

1836