D. Исследовательская выставка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы бродите по исследовательской выставке на конференции 2050.

Выставка может быть представлена как неориентированный взвешенный граф в виде сетки размера $$$n\times m$$$. Множество вершин графа это $$$\{(i, j)|1\le i\le n, 1\le j\le m\}$$$. Две вершины $$$(i_1,j_1)$$$ и $$$(i_2, j_2)$$$ соединены ребром, если и только если $$$|i_1-i_2|+|j_1-j_2|=1$$$.

На каждом ходу вы можете перейти из вершины в любую другую вершину, соединенную ребром с текущей. На каждом ребре расположено несколько экспонатов. Так как вы их все уже видели, то при проходе по ребру, на котором расположено $$$x$$$ экспонатов, ваша скукота увеличивается на $$$x$$$.

Для каждой стартовой вершины $$$(i, j)$$$ найдите ответ на следующий вопрос: чему равна минимальная возможная скукота, если вы начнете в вершине $$$(i, j)$$$ и вернетесь обратно, сделав ровно $$$k$$$ ходов.

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

Входные данные

Первая строка содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$2\leq n, m\leq 500, 1\leq k\leq 20$$$).

$$$j$$$-е число ($$$1\le j \le m - 1$$$) в $$$i$$$-й из следующих $$$n$$$ строк равно количеству экспонатов, расположенных на ребре между вершинами $$$(i, j)$$$ и $$$(i, j+1)$$$.

$$$j$$$-е число ($$$1\le j\le m$$$) в $$$i$$$-й из следующих $$$n-1$$$ строк равно количеству экспонатов, расположенных на ребре между вершинами $$$(i, j)$$$ и $$$(i+1, j)$$$.

На каждом ребре находится от $$$1$$$ до $$$10^6$$$ экспонатов.

Выходные данные

Выведите $$$n$$$ строк по $$$m$$$ чисел в каждой. $$$j$$$-е число в $$$i$$$-й строке, $$$answer_{ij}$$$, должно равняться минимальной возможной скукоте, если вы начнете в вершине $$$(i, j)$$$ и вернетесь обратно, сделав ровно $$$k$$$ ходов.

Если вы не можете вернуться обратно в вершину $$$(i, j)$$$, сделав ровно $$$k$$$ ходов, $$$answer_{ij}$$$ должен равняться $$$-1$$$.

Примеры
Входные данные
3 3 10
1 1
1 1
1 1
1 1 1
1 1 1
Выходные данные
10 10 10
10 10 10
10 10 10
Входные данные
2 2 4
1
3
4 2
Выходные данные
4 4
10 6
Входные данные
2 2 3
1
2
3 4
Выходные данные
-1 -1
-1 -1
Примечание

В первом примере ответ всегда равен $$$10$$$ вне зависимости от того, как вы пойдете.

Во втором примере $$$answer_{21} = 10$$$, путь может быть таким: $$$(2,1) \to (1,1) \to (1,2) \to (2,2) \to (2,1)$$$, скукота равна $$$4 + 1 + 2 + 3 = 10$$$.