Kaguya Wants to Receive Flowers

Cerință

Kaguya nu a primit niciodată flori de la Miyuki (...și trebuie să schimbam asta cât mai curând!). În primul rand, din buzunarele adânci ale conglomeratului de afaceri Shinomiya, Kaguya a făcut o donație generoasă pentru restaurarea grădinii Academiei Shuchi’in, unde studiază ea și Miyuki. Apoi ea plănuiește să îl ia pe Miyuki în gradină, sub pretextul de a discuta probleme ale consiliului elevilor. (Daca este înconjurat de flori, el va primi un indiciu și cu siguranță îmi va oferi un buchet!)

Gradina Academiei Shuchi’in are forma unui pătrat cu latura de $N$ metri și este împărțit în $N \cdot N$ parcele pătrate cu dimensiunea de $1$ metru. Harta grădinii arata că parcelele sunt aranjate pe linii și coloane și sunt notate cu perechi $(r, c)$, unde $r$ este linia și $c$ coloana pe care parcela o ocupa. Unele parcele, marcate cu $0$ pe harta grădinii, conțin copaci străvechi care nu au putut fi mutați sau tăiați când grădina a fost restaurata. Alte parcele, marcate cu $1$, conțin flori. Notăm cu $F$ numărul total de parcele care conțin flori. De asemenea definim distanța dintre două parcele $(r, c)$ și $(r′, c′)$ ca fiind $|r − r′| + |c − c′|$.

Kaguya definește gradul de înflorire a unei parcele că fiind suma distanțelor de la parcela curenta la cele mai apropiate $K$ parcele care conțin flori. Ea vrea să știe gradul de înflorire al fiecărei parcele. (Daca sunt prea multe flori în jurul lui, vă fi evident pentru Miyuki ce vreau! Dar daca sunt prea puține flori, el nu vă înțelege indiciul...).

Date de intrare

Prima linie a intrării conține doua numere întregi $N$ și $K$, separate printr-un spațiu, având semnificația din enunț. Următoarele $N$ linii conțin fiecare cate $N$ cifre $0$ sau $1$, fară spații intre ele. Cifra cu numărul de ordine $j$ de pe linia $i$ vă fi $0$ daca parcela $(i, j)$ nu conține flori, sau $1$ daca conține.

Date de ieșire

Afișați $N$ linii, fiecare conținând cate $N$ numere întregi separate prin cate un spatiu: valoarea cu numărul de ordine $j$ de pe linia $i$ va reprezenta gradul de înflorire al parcelei $(i, j)$.

Restricții și precizări

• $1 \leq N \leq 1 \ 000$;
• $1 \leq K \leq F \leq N \cdot M$;
• Una dintre cele mai apropiate K parcele, care conține flori, de parcela (i, j), poate fi ea însăși daca este marcata cu 1 pe harta.

Exemplu

stdin

5 3
10111
10000
10000
01000
00010

stdout

3 4 3 2 3
2 5 5 5 6
3 4 6 7 8
4 5 6 6 8
7 6 7 7 9

Explicație

În acest exemplu, grădina are dimensiune $N = 5$ și trebuie să găsim, pentru fiecare parcelă, suma distanțelor de la parcela curentă la cele mai apropiate $K = 3$ parcele care conțin flori.
Să considerăm parcela $(4, 2)$, de pe linia 4, coloana 2. Aceasta parcelă este marcată cu 1, și prin urmare conține flori. Cele mai apropiate $K = 3$ parcele, care conțin flori, de parcela $(4, 2)$ sunt:

• $(4, 2)$ (aceiasi parcela), la distanța |4 − 4| + |2 − 2| = 0 + 0 = 0
• $(3, 1)$, la distanța |4 − 3| + |2 − 1| = 1 + 1 = 2
• $(5, 4)$, la distanța |4 − 5| + |2 − 4| = 1 + 2 = 3.

Suma acestor distanțe este 0 + 2 + 3 = 5, și prin urmare al doilea număr de pe lina 4 pe care îl vom afișă va fi 5.
Vă rugăm să rețineți că parcela $(2, 1)$ conține de asemnea flori și se găsește la o distanță de 3 de parcela $(4, 2)$ (aceiași distanță că și până la parcela $(5, 4)$), dar pentru că am găsit deja $K = 3$ parcele care sunt la fel de aproape sau mai aproape, nu trebuie să includem și parcela $(2, 1)$ în calculul distanței.