{"raw_statement":[{"iden":"statement","content":"小 C 在 C 国旅行。\n\nC 国有 $n\\times m$ 个城市，可以看做 $n\\times m$ 的网格。定义 $(i,j)$ 表示在网格中第 $i$ 行第 $j$ 列的城市。\n\n该国有 $2$ 种交通系统：\n\n* 对于所有 $1\\leq i<n,1\\leq j\\leq m$，$(i,j)$ 到 $(i+1,j)$ 有一段由 L 公司修的单向铁路；\n* 对于所有 $1\\leq i\\leq n,1\\leq j<m$，$(i,j)$ 到 $(i,j+1)$ 有一段由 Z 公司修的单向铁路；\n\n在每一个城市有一个售票口，$(i,j)$ 城市的售票口可以用 $a_{i,j}$ 元购买一张 L 公司的铁路票，$b_{i,j}$ 元购买一张 Z 公司的铁路票。当你拥有一个公司的一张铁路票时，你可以乘坐这个公司的任意一段铁路，并消耗掉这张铁路票。注意，一张铁路票可以且仅可以使用一次。\n\n小 C 原来在城市 $(1,1)$。他想要在 C 国旅游，但是他不想浪费任何的钱（即，当他旅游完毕时手上不应该有多余的车票）。对于所有 $1\\leq x\\leq n,1\\leq y\\leq m$，求他花 $k$ 元钱并在城市 $(x,y)$ 结束旅行的方案数，对 $998\\ 244\\ 353$ 取模。\n\n两种旅行方案不同，当且仅当小 C 经过的城市不同，或他在某一个城市购买的某家公司的铁路票数量不同。"},{"iden":"input","content":"从标准输入读入数据。\n\n输入的第一行包含三个正整数 $n,m,k$，表示网格的大小和钱的数目。\n\n接下来 $n$ 行，每行 $m$ 个正整数，第 $i$ 行第 $j$ 个正整数表示 $a_{i,j}$。\n\n接下来 $n$ 行，每行 $m$ 个正整数，第 $i$ 行第 $j$ 个正整数表示 $b_{i,j}$。"},{"iden":"output","content":"输出到标准输出。\n\n输出一共 $n$ 行，每行 $m$ 个整数，表示到每个点钱恰好花完并结束旅行的方案数，对 $998\\ 244\\ 353$ 取模。"},{"iden":"note","content":"**【样例解释 #1】**\n\n到 $(3,1)$ 的方案有：\n\n* 在 $(1,1)$ 购买 $1$ 张 L 公司的铁路票；乘坐 L 公司的铁路到 $(2,1)$；在 $(2,1)$ 购买 $1$ 张 L 公司的铁路票；乘坐 L 公司的铁路到 $(3,1)$。\n\n到 $(2,2)$ 的方案有：\n\n* 在 $(1,1)$ 购买 $1$ 张 L 公司的铁路票；乘坐 L 公司的铁路到 $(2,1)$；在 $(2,1)$ 购买 $1$ 张 Z 公司的铁路票；乘坐 Z 公司的铁路到 $(2,2)$。\n\n到 $(3,2)$ 的方案有：\n\n* 在 $(1,1)$ 购买 $1$ 张 Z 公司的铁路票；乘坐 Z 公司的铁路到 $(1,2)$；在 $(1,2)$ 购买 $2$ 张 L 公司的铁路票；乘坐 L 公司的铁路到 $(2,2)$；乘坐 L 公司的铁路到 $(3,2)$。\n* 在 $(1,1)$ 购买 $1$ 张 L 公司的铁路票和 $1$ 张 Z 公司的铁路票；乘坐 Z 公司的铁路到 $(1,2)$；乘坐 L 公司的铁路到 $(2,2)$；在 $(2,2)$ 购买 $1$ 张 L 公司的铁路票；乘坐 L 公司的铁路到 $(3,2)$。\n* 在 $(1,1)$ 购买 $1$ 张 L 公司的铁路票和 $1$ 张 Z 公司的铁路票；乘坐 L 公司的铁路到 $(2,1)$；乘坐 Z 公司的铁路到 $(2,2)$；在 $(2,2)$ 购买 $1$ 张 L 公司的铁路票；乘坐 L 公司的铁路到 $(3,2)$。\n\n到 $(2,3)$ 的方案有：\n\n* 在 $(1,1)$ 购买 $1$ 张 L 公司的铁路票和 $2$ 张 Z 公司的铁路票。在此之后，有 $3$ 种方案可以从 $(1,1)$ 乘坐两公司的铁路到 $(2,3)$。\n* 在 $(1,1)$ 购买 $1$ 张 Z 公司的铁路票；乘坐 Z 公司的铁路到 $(1,2)$；在 $(1,2)$ 购买 $1$ 张 L 公司的铁路票和 $1$ 张 Z 公司的铁路票。在此之后，有 $2$ 种方案可以从 $(1,2)$ 乘坐两公司的铁路到 $(2,3)$。\n\n**【样例 #2】**\n\n见选手目录下的 `travel/travel2.in` 与 `travel/travel2.ans`。这个样例满足测试点 $7\\sim 8$ 的条件限制。\n\n**【样例 #3】**\n\n见选手目录下的 `travel/travel3.in` 与 `travel/travel3.ans`。这个样例满足测试点 $11$ 的条件限制。\n\n**【数据范围】**\n\n对于所有数据保证：$1\\leq n,m\\leq45$，$1\\leq k,a_{i,j},b_{i,j}\\leq90$。\n\n| 测试点编号 | $n,m$ | $k$ | $a_{i,j}$ | $b_{i,j}$ |\n|:--:|:--:|:--:|:--:|:--:|\n| $1\\sim3$ | $\\leq3$ | $\\leq5$ | $=1$ | $=1$ |\n| $4\\sim6$ | $\\leq10$ | $\\leq10$ | $=1$ | $=40$ |\n| $7\\sim8$ | $\\leq40$ | $\\leq30$ | $=1$ | $=45$ |\n| $9\\sim10$ | $\\leq15$ | $\\leq15$ | $\\leq15$ | $\\leq15$ |\n| $11$ | $\\leq15$ | $\\leq30$ | $\\leq30$ | $\\leq30$ |\n| $12$ | $\\leq20$ | $\\leq40$ | $\\leq40$ | $\\leq40$ |\n| $13\\sim15$ | $\\leq25$ | $\\leq50$ | $\\leq50$ | $\\leq50$ |\n| $16$ | $\\leq30$ | $\\leq60$ | $\\leq60$ | $\\leq60$ |\n| $17$ | $\\leq35$ | $\\leq70$ | $\\leq70$ | $\\leq70$ |\n| $18\\sim19$ | $\\leq40$ | $\\leq80$ | $\\leq80$ | $\\leq80$ |\n| $20$ | $\\leq45$ | $\\leq90$ | $\\leq90$ | $\\leq90$ |"}],"translated_statement":null,"sample_group":[["3 3 5\n3 2 1\n2 1 3\n1 3 2\n1 2 3\n2 3 1\n3 1 2","0 0 0\n0 1 5\n1 3 5"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}