노을

어느 도시의 주민들은 집 옥상에서 노을 보는 것을 좋아한다. 특히 멋진 노을이 질 때면 더 좋은 전망을 얻으려고 가까운 건물 옥상에 올라가는 사람도 있다.

이 도시의 건물들은 $n \times n$ 격자 위에 놓여 있고, 두 건물 사이의 거리는 맨해튼 거리로 잰다.

John은 새 집을 사려고 한다. 노을을 무척 좋아해서 더 좋은 전망을 위해 매일 저녁 다른 건물까지 걸어갈 생각이지만, 자기 집에서 $k$ 칸보다 멀리 걸어가지는 않으려 한다.

각 건물 $a$에 대해, John이 그 건물에 집을 산다고 할 때 걸어갈 수 있는(맨해튼 거리가 $k$ 이하이며 건물 $a$ 자신을 포함하는) 건물 중 가장 높은 건물의 높이를 구하라. 그 높이들로 이루어진 새 지도를 출력한다.

참고로 두 점 $(a_x, a_y)$와 $(b_x, b_y)$ 사이의 맨해튼 거리는 $\rho((a_x, a_y), (b_x, b_y)) = |a_x - b_x| + |a_y - b_y|$ 이다.

첫째 줄에 두 정수 $n$과 $k$ ($1 \le n \le 1500$, $1 \le k \le n$)가 공백 하나로 구분되어 주어진다. 이어지는 $n$개의 줄에는 각각 $n$개의 음이 아닌 정수가 공백 하나로 구분되어 주어진다. 각 값은 $10^9$ 이하이며, 건물의 높이를 행 순서대로 나타낸다.

$n$개의 줄을 출력한다. 각 줄에는 $n$개의 음이 아닌 정수를 공백 하나로 구분하여 출력한다. $i$행 $j$열의 값은 건물 $(i, j)$로부터 맨해튼 거리가 $k$ 이하인 건물들 중 가장 높은 건물의 높이이다.