您正在2050年会议的探索空间中徘徊。
浏览器空间可以被视为大小为 $$$n\times m$$$ 的无向加权网格图。顶点集为 $$$\{(i, j)|1\le i\le n, 1\le j\le m\}$$$。当且仅当 $$$|i_1-i_2|+|j_1-j_2|=1$$$ 时,两个顶点 $$$(i_1,j_1)$$$ 和 $$$(i_2, j_2)$$$ 通过边连接。
在每一步中,您都可以走到由边与当前顶点连接的任何顶点。每条边缘都有一定数量的展品。由于您已经知道所有展品,因此每当您经过包含 $$$x$$$ 展品的边缘时,您的无聊感就会增加 $$$x$$$。
对于每个起始顶点 $$$(i, j)$$$,请回答以下问题:如果您从 $$$(i, j)$$$ 步行并在恰好 $$$k$$$ 步后返回到它,那么最小可能的无聊度是多少?
您可以多次使用任何边,但这些边上的无聊度也会被多次计数。在每一步中,您都不能停留在当前顶点。在穿过边缘时您也无法改变方向。在 $$$k$$$ 步骤后返回到起始顶点 $$$(i, j)$$$ 之前,您可以自由地访问 $$$(i, j)$$$ (或不)。
输入
第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$2\leq n, m\leq 500, 1\leq k\leq 20$$$)。
以下 $$$n$$$ 行的第 $$$i$$$ 行中的第 $$$j$$$ 数字 ($$$1\le j \le m - 1$$$) 是顶点 $$$(i, j)$$$ 和顶点 $$$(i, j+1)$$$ 之间的边上的存在位数。
以下 $$$n-1$$$ 行的第 $$$i$$$ 行中的第 $$$j$$$ 个数字 ($$$1\le j\le m$$$) 是顶点 $$$(i, j)$$$ 和顶点 $$$(i+1, j)$$$ 之间的边上的存在位数。
每条边上的展品数量是 $$$1$$$ 和 $$$10^6$$$ 之间的整数。
输出
输出 $$$n$$$ 行,每行包含 $$$m$$$ 数字。如果您从 $$$(i, j)$$$ 开始,并在恰好 $$$k$$$ 步后返回,则第 $$$i$$$ 行中的第 $$$j$$$ 数字 $$$answer_{ij}$$$ 应该是可能的最小无聊度。
如果在 $$$k$$$ 步之后无法返回到顶点 $$$(i, j)$$$,则 $$$answer_{ij}$$$ 应为 $$$-1$$$。
示例
输入 #1
3 3 10 1 1 1 1 1 1 1 1 1 1 1 1
输出 #1
10 10 10 10 10 10 10 10 10
输入 #2
2 2 4 1 3 4 2
输出 #2
4 4 10 6
输入 #3
2 2 3 1 2 3 4
输出 #3
-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$$$。