#L9743. 洛谷模拟「KDOI-06-J」旅行

洛谷模拟「KDOI-06-J」旅行

「KDOI-06-J」旅行

题目描述

小 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) 城市的售票口可以用 ai,ja_{i,j} 元购买一张 L 公司的铁路票,bi,jb_{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 个正整数表示 ai,ja_{i,j}

接下来 nn 行,每行 mm 个正整数,第 ii 行第 jj 个正整数表示 bi,jb_{i,j}

输出格式

输出到标准输出。

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

【样例 #2】

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

【样例 #3】

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

【数据范围】

对于所有数据保证:1n,m451\leq n,m\leq451k,ai,j,bi,j901\leq k,a_{i,j},b_{i,j}\leq90

测试点编号 n,mn,m kk ai,ja_{i,j} bi,jb_{i,j}
131\sim3 3\leq3 5\leq5 =1=1 =1=1
464\sim6 10\leq10 =40=40
787\sim8 40\leq40 30\leq30 =45=45
9109\sim10 15\leq15 15\leq15
1111 30\leq30
1212 20\leq20 40\leq40
131513\sim15 25\leq25 50\leq50
1616 30\leq30 60\leq60
1717 35\leq35 70\leq70
181918\sim19 40\leq40 80\leq80
2020 45\leq45 90\leq90