Bob really likes triangles. His costume's a triangle, he only trick-or-treats triangular houses, and of course, arranges his candy in a big triangle!

Bob has an ~N\times N~ grid of cells where he can place candy in. Each cell has a value attached to it, denoted by ~G_{i,j}~. Additionally, he wants to place all of his candy in a right triangle with the two legs at the bottom and left of the triangle. To commemorate his ~B~-th birthday last week, he would like the triangle's hypoteneuse to have a slope of ~-\frac1B~. In other words, each row should be ~B~ cells longer than the previous row, where the topmost row has ~1~ cell. Additionally, he would like the triangle to have ~R~ rows to fit all of his candy. Obviously, the entire triangle must fit inside the grid.

Now, he is thinking about how to position his triangle. For each triangle, its score is the maximum value of all the cells that it covers. He hopes to calculate, for each position of the triangle, what its score is.

For this problem, the test data is rather large - consider using BufferedReader if you are using Java and disabling synchronization if you are using C++. This problem has only been tested on Java and C++.

Constraints

For all subtasks:

~1\le N \le 1500~

~1\le B\le N~

~1\le R\le N~

~1 + (R-1)B\le N~ (at least one triangle fits in the grid)

~1\le G_{i,j}\le 10^6~

Subtask 1[20%]

~N\le 500~

Subtask 2[80%]

No additional constraints

Input Specification

The first line has three integers: ~N~, ~B~, and ~R~.

The next ~N~ lines each contain ~N~ integers: the values of the cells in Bob's ~N\times N~ grid. The first character is the leftmost column and the last row is the bottommost row.

Output Specification

~N~ lines with ~N~ integers each: the score of the triangle if its bottom left corner was positioned at each cell. If a triangle will not fit there, then output 0 at that cell.

Sample Input

7 2 3
7 2 4 2 1 7 9
8 3 7 2 6 8 2
3 8 2 5 7 3 7
1 9 4 8 3 6 7
3 5 6 2 4 6 4
9 5 7 2 8 4 6
7 8 2 6 7 4 4

Sample Output

0 0 0 0 0 0 0
0 0 0 0 0 0 0
8 8 7 0 0 0 0
9 9 8 0 0 0 0
9 9 8 0 0 0 0
9 9 8 0 0 0 0
9 8 8 0 0 0 0

Sample Explanation

The first row of the triangle has length ~1~, the second row has length ~1+2=3~, and the third row has length ~3+2=5~

With that, the first two rows (height less than 3) and last four columns (width less than 5) cannot be the bottom left corner of a triangle.

Then, for example, at the third row and third column, the triangle looks as such:

The maximum value the triangle covers is 7, so the third row and third column will have value 7.

As for another example, consider the triangle with its bottom left corner at the bottom row and third column:

The maximum value the triangle covers is 8, so the bottom row and third column has value 8.