Traveling in C Country

In C Country there is an (n \times m) grid of cities. We denote ((i,j)) as the city in the (i)th row and (j)th column. There are two types of one‐way railways:

• For all \(1 \le i < n\) and \(1 \le j \le m\), there is a one–way railway built by the L company from \((i,j)\) to \((i+1,j)\).
• For all \(1 \le i \le n\) and \(1 \le j < m\), there is a one–way railway built by the Z company from \((i,j)\) to \((i,j+1)\).

Each city has two ticket booths. At city ((i,j)) one can buy an L–ticket for (a_{i,j}) yuan and a Z–ticket for (b_{i,j}) yuan. When you own a ticket from a company, you may use it on any railway segment of that company; however, the ticket is used up immediately after one use. Note that a ticket can be used at most once.

Initially, you are in city ((1,1)) with no tickets. You plan to travel, but you dislike wasting money – that is, when your tour is over you should not have any unused tickets. Along your journey you can purchase tickets arbitrarily; even if two journeys pass through the same sequence of cities, they are considered different if there is at least one city where the number of tickets purchased from one company differs.

Once you decide on a travel plan, your route is a monotonic path (only moving down or right) starting at ((1,1)). Suppose the journey contains (L) moves. For each move, you must decide from which of the already visited cities (including the current one) you bought the corresponding ticket. Specifically, if the move is vertical (using an L–ticket) then if it is the (r)th move on your route, the contribution to the total cost is chosen from ({a_{u,v}}) for every city ((u,v)) that appears in the first (r) cities of your path; similarly, for a horizontal move (using a Z–ticket) the cost is chosen from the corresponding (b)–values.

Given an integer (k), for every city ((x,y)) ( (1 \le x \le n,; 1 \le y \le m)) you are to compute, modulo (998244353), the number of travel plans that end at ((x,y)) and have a total cost exactly (k) yuan.

The input format and output format are described below.

inputFormat

The first line contains three integers (n), (m), and (k) (the dimensions of the grid and the target total cost).

Then follow (n) lines, each containing (m) integers. The (j)th integer on the (i)th line is (a_{i,j}), the cost to purchase an L–ticket at city ((i,j)).

Then follow (n) lines, each containing (m) integers. The (j)th integer on the (i)th line is (b_{i,j}), the cost to purchase a Z–ticket at city ((i,j)).

outputFormat

Output (n) lines, each containing (m) integers. The (j)th integer on the (i)th line should be the number (modulo (998244353)) of travel plans which end at city ((i,j)) and cost exactly (k) yuan.

sample

1 1 0
3
5

1