「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$ 取模。

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

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$ | $\leq10$ | $=1$ | $=40$ | | $7\sim8$ | $\leq40$ | $\leq30$ | $=1$ | $=45$ | | $9\sim10$ | $\leq15$ | $\leq15$ | $\leq15$ | $\leq15$ | | $11$ | $\leq15$ | $\leq30$ | $\leq30$ | $\leq30$ | | $12$ | $\leq20$ | $\leq40$ | $\leq40$ | $\leq40$ | | $13\sim15$ | $\leq25$ | $\leq50$ | $\leq50$ | $\leq50$ | | $16$ | $\leq30$ | $\leq60$ | $\leq60$ | $\leq60$ | | $17$ | $\leq35$ | $\leq70$ | $\leq70$ | $\leq70$ | | $18\sim19$ | $\leq40$ | $\leq80$ | $\leq80$ | $\leq80$ | | $20$ | $\leq45$ | $\leq90$ | $\leq90$ | $\leq90$ |