Kaguya nu a primit niciodată flori de la Miyuki (…și trebuie să schimbăm asta cât mai curând!). În primul rând, din buzunarele adânci ale conglomeratului de afaceri Shinomiya, Kaguya a făcut o donat,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 grădină, sub pretextul de a discuta probleme ale consiliului elevilor. (Dacă este înconjurat de flori, el va primi un indiciu și cu siguranță îmi va oferi un buchet!)

Grădina Academiei Shuchi’in are forma unui pătrat cu latura de N metri și este împărțit în N × N parcele pătrate cu dimensiunea de 1 metru. Harta grădinii arată că parcelele sunt aranjate pe linii și coloane și sunt notate cu perechi (r, c), unde r este linia și c coloana pe care o ocupă parcela. 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 restaurată. 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′|.

Cerința

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

Date de intrare

Prima linie a intrării conține două numere întregi N și K, separate printr-un spațiu, având semnificația din enunț. Următoarele N linii conțin fiecare câte N cifre 0 sau 1, fără spații între ele. Cifra cu numărul de ordine j de pe linia i va fi 0 dacă parcela (i, j) nu conține flori, sau 1 dacă conține.

Date de ieșire

Afișați N linii, fiecare conținând câte N numere întregi separate prin câte un spațiu: 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 ≤ N ≤ 1 000
• 1 ≤ K ≤ F ≤ N × N
• Una dintre cele mai apropiate K parcele, care conține flori, de parcela (i, j), poate fi ea insăși dacă este marcată cu 1 pe hartă.

Exemplu:

Intrare

5 3
10111
10000
10000
01000
00010

Ieșire

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. Această 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) (aceiași parcelă), la distanța |4 − 4| + |2 − 2| = 0 + 0 = 0,
• (3, 1), la distanța |4 − 3| + |2 − 1| = 1 + 1 = 2 și
• (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șa 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ță 3 de parcela (4, 2) (aceiași distanță ca ș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.