Sunsets

Residents of a small city love watching sunsets from the rooftops of their houses. When a sunset is especially spectacular, some of them climb onto the roofs of nearby buildings to get a better view.

The city's buildings sit on an $n \times n$ grid, and the distance between two buildings is measured with the Manhattan metric.

John is about to buy a new flat. He loves sunsets and is willing to walk to another building every evening for a better view, but he will not walk more than $k$ units away from his own flat.

For each building $a$, determine the height of the tallest building John could walk to (every building within Manhattan distance $k$, including building $a$ itself) if he bought his flat in building $a$. Output the resulting map of these heights.

As a reminder, the Manhattan distance between two points $(a_x, a_y)$ and $(b_x, b_y)$ is $\rho((a_x, a_y), (b_x, b_y)) = |a_x - b_x| + |a_y - b_y|$.

The first line contains two integers $n$ and $k$ ($1 \le n \le 1500$, $1 \le k \le n$) separated by a single space. Each of the next $n$ lines contains $n$ non-negative integers, each at most $10^9$, separated by single spaces; these are the heights of the buildings, given row by row.

Print $n$ lines, each containing $n$ non-negative integers separated by single spaces. The integer in row $i$, column $j$ is the height of the tallest building within Manhattan distance $k$ of building $(i, j)$.