Inhabitants of Bytetown love watching sunsets from the roofs of their houses. If a sunset is particularly spectacular, some of them decide to go on the roofs of nearby buildings, so that they have a better view.

Buildings in Bytetown capital are arranged on a grid $ n $ × $ n $. Distance between two points is measured using the Manhattan metric.

John plans to buy a new flat. He is a great admirer of sunsets and he is ready to walk to some other building every day to see this inimitable phenomenon. He would not like, however, to walk further than $ k $ units away from his flat.

Help John decide where to buy his new flat. For a given plan of the city with heights of all buildings specified, construct a new map, which for each building $ a $ specifies the height of the highest building that John can walk to, assuming that he buys a flat in building $ a $.

Write a program which:

• reads from the standard input the plan of the city with heights of all buildings specified,
• for each building calculates the height of the highest building located not further than $ k $ units away from it,
• writes the modified map with calculated heights to the standard output.

As a reminder, the Manhattan distance of two points $(a_x, a_y)$ and $(b_x, b_y))$ is $ρ((a_{x}, a_{y}), (b_{x}, b_{y})) = |a_{x} - b_{x}| + |a_{y} - b_{y}|$.

Input Format

In the first line of the standard input there are two integers $ n $ and $ k $ (1 ≤ $ n $ ≤ 1500, 1 ≤ $ k $ ≤ $ n $), separated by a single space. In each of the following $ n $ lines there are $ n $ non-negative integers not grater than 1 000 000 000, separated by single spaces - they describe the plan of Bytetown.

Output Format

In each of $ n $ lines of standard output there should be $ n $ non-negative integers, separated by single spaces and describing the modified plan of Bytetown.

Example

Input

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

Output

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