83872 - 旅行

时间限制 2 秒 内存限制 128 MB

题目描述

小 C 在 C 国旅行。

C 国有 $n\times m$ 个城市，可以看做 $n\times m$ 的网格。定义 $(i,j)$ 表示在网格中第 $i$ 行第 $j$ 列的城市。

该国有 $2$ 种交通系统：

对于所有 $1\leq i < n,1\leq j\leq m$ ， $(i,j)$ 到 $(i+1,j)$ 有一段由 L 公司修的单向铁路；
对于所有 $1\leq i\leq n,1\leq j < m$ ， $(i,j)$ 到 $(i,j+1)$ 有一段由 Z 公司修的单向铁路；

在每一个城市有一个售票口， $(i,j)$ 城市的售票口可以用 $a(i,j)$ 元购买一张 L 公司的铁路票， $b(i,j)$ 元购买一张 Z 公司的铁路票。当你拥有一个公司的一张铁路票时，你可以乘坐这个公司的任意一段铁路，并消耗掉这张铁路票。注意，一张铁路票可以且仅可以使用一次。

小 C 原来在城市 $(1,1)$ 。他想要在 C 国旅游，但是他不想浪费任何的钱（即，当他旅游完毕时手上不应该有多余的车票）。对于所有 $1\leq x\leq n,1\leq y\leq m$ ，求他花 $k$ 元钱并在城市 $(x,y)$ 结束旅行的方案数，对 $998\ 244\ 353$ 取模。

两种旅行方案不同，当且仅当小 C 经过的城市不同，或他在某一个城市购买的某家公司的铁路票数量不同。

输入

输入的第一行包含三个正整数 $n,m,k$ ，表示网格的大小和钱的数目。

接下来 $n$ 行，每行 $m$ 个正整数，第 $i$ 行第 $j$ 个正整数表示 $a(i,j)$ 。

接下来 $n$ 行，每行 $m$ 个正整数，第 $i$ 行第 $j$ 个正整数表示 $b(i,j)$ 。

输出

输出一共 $n$ 行，每行 $m$ 个整数，表示到每个点钱恰好花完并结束旅行的方案数，对 $998\ 244\ 353$ 取模。

样例

样例 1

输入

输出

0 0 0
0 1 5
1 3 5

提示

【样例解释 #1】

到 $(3,1)$ 的方案有：

在 $(1,1)$ 购买 $1$ 张 L 公司的铁路票；乘坐 L 公司的铁路到 $(2,1)$ ；在 $(2,1)$ 购买 $1$ 张 L 公司的铁路票；乘坐 L 公司的铁路到 $(3,1)$ 。

到 $(2,2)$ 的方案有：

在 $(1,1)$ 购买 $1$ 张 L 公司的铁路票；乘坐 L 公司的铁路到 $(2,1)$ ；在 $(2,1)$ 购买 $1$ 张 Z 公司的铁路票；乘坐 Z 公司的铁路到 $(2,2)$ 。

到 $(3,2)$ 的方案有：

在 $(1,1)$ 购买 $1$ 张 Z 公司的铁路票；乘坐 Z 公司的铁路到 $(1,2)$ ；在 $(1,2)$ 购买 $2$ 张 L 公司的铁路票；乘坐 L 公司的铁路到 $(2,2)$ ；乘坐 L 公司的铁路到 $(3,2)$ 。
在 $(1,1)$ 购买 $1$ 张 L 公司的铁路票和 $1$ 张 Z 公司的铁路票；乘坐 Z 公司的铁路到 $(1,2)$ ；乘坐 L 公司的铁路到 $(2,2)$ ；在 $(2,2)$ 购买 $1$ 张 L 公司的铁路票；乘坐 L 公司的铁路到 $(3,2)$ 。
在 $(1,1)$ 购买 $1$ 张 L 公司的铁路票和 $1$ 张 Z 公司的铁路票；乘坐 L 公司的铁路到 $(2,1)$ ；乘坐 Z 公司的铁路到 $(2,2)$ ；在 $(2,2)$ 购买 $1$ 张 L 公司的铁路票；乘坐 L 公司的铁路到 $(3,2)$ 。

到 $(2,3)$ 的方案有：

在 $(1,1)$ 购买 $1$ 张 L 公司的铁路票和 $2$ 张 Z 公司的铁路票。在此之后，有 $3$ 种方案可以从 $(1,1)$ 乘坐两公司的铁路到 $(2,3)$ 。
在 $(1,1)$ 购买 $1$ 张 Z 公司的铁路票；乘坐 Z 公司的铁路到 $(1,2)$ ；在 $(1,2)$ 购买 $1$ 张 L 公司的铁路票和 $1$ 张 Z 公司的铁路票。在此之后，有 $2$ 种方案可以从 $(1,2)$ 乘坐两公司的铁路到 $(2,3)$ 。

对于所有数据保证： $1\leq n,m\leq45$ ，$1\leq k,a{i,j},b{i,j}\leq90$。

来源

KDOI