「KDOI-06-J」旅行

题目描述

小 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

样例输入 #1

3 3 5
3 2 1
2 1 3
1 3 2
1 2 3
2 3 1
3 1 2

样例输出 #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)$。

【样例 #2】

见选手目录下的 travel/travel2.in 与 travel/travel2.ans。这个样例满足测试点 $7\sim 8$ 的条件限制。

【样例 #3】

见选手目录下的 travel/travel3.in 与 travel/travel3.ans。这个样例满足测试点 $11$ 的条件限制。

【数据范围】

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

测试点编号	$n,m$	$k$	$a_{i,j}$	$b_{i,j}$
$1\sim3$	$\leq3$	$\leq5$	$=1$	$=1$
$4\sim6$	$\leq10$			$=40$
$7\sim8$	$\leq40$	$\leq30$		$=45$
$9\sim10$	$\leq15$	$\leq15$
$11$		$\leq30$
$12$	$\leq20$	$\leq40$
$13\sim15$	$\leq25$	$\leq50$
$16$	$\leq30$	$\leq60$
$17$	$\leq35$	$\leq70$
$18\sim19$	$\leq40$	$\leq80$
$20$	$\leq45$	$\leq90$