P9743 "KDOI-06-J" Travel

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

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 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$.

**[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$. | Test Point ID | $n,m$ | $k$ | $a_{i,j}$ | $b_{i,j}$ | |:--:|:--:|:--:|:--:|:--:| | $1\sim3$ | $\leq3$ | $\leq5$ | $=1$ | $=1$ | | $4\sim6$ | $\leq10$ | $\leq10$ | $=1$ | $=40$ | | $7\sim8$ | $\leq40$ | $\leq30$ | $=1$ | $=45$ | | $9\sim10$ | $\leq15$ | $\leq15$ | $\leq15$ | $\leq15$ | | $11$ | $\leq15$ | $\leq30$ | $\leq30$ | $\leq30$ | | $12$ | $\leq20$ | $\leq40$ | $\leq40$ | $\leq40$ | | $13\sim15$ | $\leq25$ | $\leq50$ | $\leq50$ | $\leq50$ | | $16$ | $\leq30$ | $\leq60$ | $\leq60$ | $\leq60$ | | $17$ | $\leq35$ | $\leq70$ | $\leq70$ | $\leq70$ | | $18\sim19$ | $\leq40$ | $\leq80$ | $\leq80$ | $\leq80$ | | $20$ | $\leq45$ | $\leq90$ | $\leq90$ | $\leq90$ | Translated by ChatGPT 5