Mapa gestosci

Limit pamięci: 32 MB

Dane są:

• liczby naturalne ,
• - tabelka wypełniona liczbami ze zbioru ; kolumny i wiersze tabelki są ponumerowane od 1 do ; liczbę znajdującą sie w -tej kolumnie i -tym wierszu tabelki oznaczamy przez .

Należy obliczyć tabelkę , (do elementów tej tabelki odwołujemy się tak samo, jak do elementów tabelki ) taką, że jest sumą wszystkich liczb z tabelki leżących w odległości co najwyżej od .

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia liczby oraz tabelkę ,
• obliczy tabelkę ,
• wypisze ją na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie dodatnie liczby całkowite oddzielone pojedynczą spacją: i , gdzie .

W kolejnych wierszach znajduje się opis tabelki . Każdy z tych wierszy zawiera liczb ze zbioru , pooddzielanych pojedynczymi odstępami, -ta liczba zapisana w -szym wierszu to .

Wyjście

Standardowe wyjście powinno zawierać dokładnie wierszy, w -tym wierszu powinny być zapisane kolejno wartości pooddzielane pojedynczymi odstępami.

Przykład

Dla danych wejściowych:

5 1
1 0 0 0 1
1 1 1 0 0
1 0 0 0 0
0 0 0 1 1
0 1 0 0 0

poprawną odpowiedzią jest:

3 4 2 2 1
4 5 2 2 1
3 4 3 3 2
2 2 2 2 2
1 1 2 2 2

Autor zadania: Tomasz Śmigielski.