Задача I. Image correction ≡

Автор:A. Baranov   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

Матрица фотоаппарата представляет собой прямоугольную таблицу размерности [n × m], состоящую из светочувствительных элементов (ячеек). В момент съемки каждой ячейке такой таблицы ставится в соответствие вещественное значение Xi j, указывающее ее состояние (интенсивность).

Известно, что при считывании состояния отдельно взятой ячейки к нему добавляется взвешенная сумма состояний окружающих ее ячеек, которые формируют упорядоченный набор слоев (см. рисунок). При этом каждый последующий слой имеет в два раза меньшее влияние, чем предыдущий.

Коэффициент влияния каждой такой ячейки на полученное значение равен 1 / (2l ⋅ Nl), где l — номер содержащего ее слоя, Nl — число ячеек в l-м слое.

Также для отдельно взятой модели фотоаппарата известно максимальное число слоев k, оказывающих влияние на результат измерения.

Для заданной матрицы Y, полученной в результате измерений, и радиуса воздействия k требуется восстановить исходные значения Xi j.

Значения фиктивных ячеек (лежащих за пределами матрицы) полагаются равными нулю.

Формат входных данных

В начале входных данных хранятся три натуральных числа: n, m и k.
Далее следует матрица результатов измерений Y, записанная в строчном формате.

Формат выходных данных

Выходные данные должны содержать восстановленную матрицу X.
Все значения должны быть указаны с точностью до 5-го знака после запятой.

Ограничения

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

Примеры тестов

№ Стандартный вход Стандартный выход
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.095s 0.016s 17