Problem I. Image correction

Author:A. Baranov   Time limit:1 sec
Input file:Standard input   Memory limit:256 Mb
Output file:Standard output  

Statement

Matrix of camera represents a rectangular table of dimensions [n × m], consisting of photosensitive elements (cells). At the moment of shooting, each cell of this table is assigned a real value Xi j, indicating its state (intensity).

It is known that when reading the state of a particular cell, a weighted sum of the states of the surrounding cells is added to it, forming an ordered set of layers (see the figure). In this case, each subsequent layer has half the influence of the previous one.

The influence coefficient of each such cell on the obtained value is equal to 1 / (2l ⋅ Nl), where l is the number of the layer containing it, and, Nl is the number of cells in the l-th layer.

Also, for a separately taken camera model, the maximum number of layers k, influencing the measurement result is known.

For a given matrix Y, obtained as a result of measurements and an impact radius k it is required to restore the original values Xi j.

The values of dummy cells (located outside the matrix) are considered to be zero.

Input format

At the beginning of the input data three natural numbers are stored: n, m и k. Then follows the matrix of measurement results Y, recorded in row format.

Output format

The output data should contain the restored matrix X. All values should be specified with an accuracy of up to 5 decimal places.

Constraints

0 ≤ Yi j ≤ 10, 0 < n ⋅ m ≤ 40 000, 0 < k ≤ 6

Sample tests

No. Standard input Standard output
1
9 6 3
0.26620 1.51042 0.59606 2.85301 0.76968 3.75000
1.51042 0.67130 3.09027 1.05324 4.38657 0.90856
0.59606 3.09027 1.13426 4.57754 1.29629 5.21412
2.88194 1.08217 4.61805 1.42940 5.60763 0.91435
0.87384 4.51388 1.43518 5.72916 1.08796 1.78819
4.13773 1.31944 5.72916 1.18055 2.03704 0.58449
0.98958 5.53819 1.12847 2.10648 0.76389 2.69097
4.98842 0.92592 1.98495 0.76389 2.95717 0.61343
0.49190 1.63773 0.54398 2.69097 0.61343 3.59375
0.00000 1.11111 0.00000 2.22222 0.00000 3.33333
1.11111 0.00000 2.22222 0.00000 3.33333 0.00000
0.00000 2.22222 0.00000 3.33333 0.00000 4.44444
2.22222 0.00000 3.33333 0.00000 4.44444 0.00000
0.00000 3.33333 0.00000 4.44444 0.00000 1.11111
3.33333 0.00000 4.44444 0.00000 1.11111 0.00000
0.00000 4.44444 0.00000 1.11111 0.00000 2.22222
4.44444 0.00000 1.11111 0.00000 2.22222 0.00000
0.00000 1.11111 0.00000 2.22222 0.00000 3.33333

0.092s 0.010s 15