3872 - 旅行

通过次数

1

提交次数

1

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

小 C 在 C 国旅行。

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

该国有 22 种交通系统:

  • 对于所有 1i<n,1jm1\leq i < n,1\leq j\leq m(i,j)(i,j)(i+1,j)(i+1,j) 有一段由 L 公司修的单向铁路;
  • 对于所有 1in,1j<m1\leq i\leq n,1\leq j < m(i,j)(i,j)(i,j+1)(i,j+1) 有一段由 Z 公司修的单向铁路;

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

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

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

输入

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

接下来 nn 行,每行 mm 个正整数,第 ii 行第 jj 个正整数表示 a(i,j)a(i,j)

接下来 nn 行,每行 mm 个正整数,第 ii 行第 jj 个正整数表示 b(i,j)b(i,j)

输出

输出一共 nn 行,每行 mm 个整数,表示到每个点钱恰好花完并结束旅行的方案数,对 998 244 353998\ 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)(3,1) 的方案有:

  • (1,1)(1,1) 购买 11 张 L 公司的铁路票;乘坐 L 公司的铁路到 (2,1)(2,1);在 (2,1)(2,1) 购买 11 张 L 公司的铁路票;乘坐 L 公司的铁路到 (3,1)(3,1)

(2,2)(2,2) 的方案有:

  • (1,1)(1,1) 购买 11 张 L 公司的铁路票;乘坐 L 公司的铁路到 (2,1)(2,1);在 (2,1)(2,1) 购买 11 张 Z 公司的铁路票;乘坐 Z 公司的铁路到 (2,2)(2,2)

(3,2)(3,2) 的方案有:

  • (1,1)(1,1) 购买 11 张 Z 公司的铁路票;乘坐 Z 公司的铁路到 (1,2)(1,2);在 (1,2)(1,2) 购买 22 张 L 公司的铁路票;乘坐 L 公司的铁路到 (2,2)(2,2);乘坐 L 公司的铁路到 (3,2)(3,2)
  • (1,1)(1,1) 购买 11 张 L 公司的铁路票和 11 张 Z 公司的铁路票;乘坐 Z 公司的铁路到 (1,2)(1,2);乘坐 L 公司的铁路到 (2,2)(2,2);在 (2,2)(2,2) 购买 11 张 L 公司的铁路票;乘坐 L 公司的铁路到 (3,2)(3,2)
  • (1,1)(1,1) 购买 11 张 L 公司的铁路票和 11 张 Z 公司的铁路票;乘坐 L 公司的铁路到 (2,1)(2,1);乘坐 Z 公司的铁路到 (2,2)(2,2);在 (2,2)(2,2) 购买 11 张 L 公司的铁路票;乘坐 L 公司的铁路到 (3,2)(3,2)

(2,3)(2,3) 的方案有:

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

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

来源

KDOI