Problem Description

Little C is traveling in Country C.

Country C has $n\times m$ cities, which can be viewed as an $n\times m$ grid. Define $(i,j)$ as the city in the $i$-th row and the $j$-th column of the grid.

There are $2$ transportation systems in this country:

• For all $1\leq i<n,1\leq j\leq m$, there is a one-way railway built by Company L from $(i,j)$ to $(i+1,j)$.
• For all $1\leq i\leq n,1\leq j<m$, there is a one-way railway built by Company Z from $(i,j)$ to $(i,j+1)$.

In each city, there is a ticket office. At the ticket office in city $(i,j)$, you can buy one railway ticket of Company L for $a_{i,j}$ yuan, and buy one railway ticket of Company Z for $b_{i,j}$ yuan. When you have one railway ticket of a company, you can take any railway segment of that company and consume that ticket. Note that one railway ticket can be used once and only once.

Little C initially is in city $(1,1)$. He wants to travel in Country C, but he does not want to waste any money (that is, when his trip ends, he should not have any extra unused tickets in hand). For all $1\leq x\leq n,1\leq y\leq m$, find the number of ways for him to spend $k$ yuan and end the trip at city $(x,y)$, modulo $998\ 244\ 353$.

Two travel plans are different if and only if the cities Little C passes through are different, or the numbers of railway tickets of some company that he buys in some city are different.

Input Format

Read data from standard input.

The first line contains three positive integers $n,m,k$, representing the grid size and the amount of money.

The next $n$ lines each contain $m$ positive integers; the $j$-th integer in the $i$-th line represents $a_{i,j}$.

The next $n$ lines each contain $m$ positive integers; the $j$-th integer in the $i$-th line represents $b_{i,j}$.

Output Format

Output to standard output.

Output a total of $n$ lines, each containing $m$ integers, representing the number of ways to end the trip at each point with exactly all the money spent, modulo $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

Hint

[Sample Explanation #1]

The plans to reach $(3,1)$ are:

• Buy $1$ Company L railway ticket at $(1,1)$; take Company L's railway to $(2,1)$; buy $1$ Company L railway ticket at $(2,1)$; take Company L's railway to $(3,1)$.

The plans to reach $(2,2)$ are:

• Buy $1$ Company L railway ticket at $(1,1)$; take Company L's railway to $(2,1)$; buy $1$ Company Z railway ticket at $(2,1)$; take Company Z's railway to $(2,2)$.

The plans to reach $(3,2)$ are:

• Buy $1$ Company Z railway ticket at $(1,1)$; take Company Z's railway to $(1,2)$; buy $2$ Company L railway tickets at $(1,2)$; take Company L's railway to $(2,2)$; take Company L's railway to $(3,2)$.
• Buy $1$ Company L railway ticket and $1$ Company Z railway ticket at $(1,1)$; take Company Z's railway to $(1,2)$; take Company L's railway to $(2,2)$; buy $1$ Company L railway ticket at $(2,2)$; take Company L's railway to $(3,2)$.
• Buy $1$ Company L railway ticket and $1$ Company Z railway ticket at $(1,1)$; take Company L's railway to $(2,1)$; take Company Z's railway to $(2,2)$; buy $1$ Company L railway ticket at $(2,2)$; take Company L's railway to $(3,2)$.

The plans to reach $(2,3)$ are:

• Buy $1$ Company L railway ticket and $2$ Company Z railway tickets at $(1,1)$. After that, there are $3$ ways to take railways of the two companies from $(1,1)$ to $(2,3)$.
• Buy $1$ Company Z railway ticket at $(1,1)$; take Company Z's railway to $(1,2)$; buy $1$ Company L railway ticket and $1$ Company Z railway ticket at $(1,2)$. After that, there are $2$ ways to take railways of the two companies from $(1,2)$ to $(2,3)$.

[Sample #2]

See travel/travel2.in and travel/travel2.ans in the contestant directory. This sample satisfies the constraints of test points $7\sim 8$.

[Sample #3]

See travel/travel3.in and travel/travel3.ans in the contestant directory. This sample satisfies the constraints of test point $11$.

[Constraints]

For all data, it is guaranteed that: $1\leq n,m\leq45$, $1\leq k,a_{i,j},b_{i,j}\leq90$.

Translated by ChatGPT 5