Bytetown 的居民喜欢在屋顶上观看日落。如果日落特别壮观，他们中的一些人会决定去附近建筑的屋顶，以便获得更好的视野。

Bytetown 首府的建筑排列在一个 $n \times n$ 的网格上。两点之间的距离使用曼哈顿距离度量。

John 计划购买一套新公寓。他非常欣赏日落，并准备每天步行到其他建筑去观看这一独特的景象。然而，他不希望步行距离超过 $k$ 个单位。

请帮助 John 决定在哪里购买他的新公寓。给定城市中所有建筑的高度，请构建一张新地图，对于每栋建筑 $a$，计算出如果 John 在建筑 $a$ 购买公寓，他所能步行到达的最高建筑的高度。

编写一个程序：

• 从标准输入读取城市中所有建筑的高度规划，
• 对于每栋建筑，计算出距离它不超过 $k$ 个单位的最高建筑的高度，
• 将计算出的高度写入标准输出。

提醒一下，两点 $(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$ 个不超过 $1\,000\,000\,000$ 的非负整数，由空格分隔，描述了 Bytetown 的城市规划。

输出格式

标准输出的 $n$ 行中，每行应包含 $n$ 个非负整数，由空格分隔，描述修改后的 Bytetown 规划。

样例

输入 1

4 2
1 3 4 5
0 2 2 3
4 1 1 3
6 2 3 0

输出 1

4 5 5 5
6 4 5 5
6 6 4 5
6 6 6 3