Problem K: Gold Rush

Problem

moritaoy君とは、コンピュータのなかで暮らしている謎の大学生です。
moritaoy君が暮らしている区画は、縦に $2^H$ 、横に $2^W$ 、の大きさのある二次元空間 $S= \{ (p,q) \in \mathbb{Z}^2 | 0 \leq p \lt 2^H, 0 \leq q \lt 2^W \} $ として表されます。
moritaoy君はいくつかの非負整数を要素とする二次元ベクトルを持っていて、この空間上を足し算を用いて移動します。
moritaoy君が $(a,b)$ にいて、ベクトル $(i,j)$ によって移動するとは、具体的には以下のような行動を示します。

• $(a+i,b+j)$ に移動する。ただし、そのような点が $S$ に存在しない場合は、オーバーフローを起こし、$a+i \equiv k \bmod 2^H , b+j \equiv l \bmod 2^W$ を満たすようなmoritaoy君の暮らす空間上の点 $(k,l) \in S$ に移動する。

以下がmoritaoy君の一日の予定です。

1. 一日を開始する。このとき、moritaoy君は $(0,0)$ にいて、疲労度は $0$ である。2.を行う。
2. 今日、moritaoy君が移動を行った回数が $K$ 以上なら4.を、そうでないなら3.か4.のどちらか一方を行う。
3. moritaoy君が持っているベクトルのなかから一つを選び、これを $v$ とする。$v$ によって移動する。moritaoy君の疲労度が $T_v$ 増加する。その後のmoritaoy君の疲労度を $T$ とし、 $T \times G_v$ 単位時間休憩する。2.を行う。
4. 一日を終了する。

moritaoy君は、色々な予定を立てて遊ぶことにしました。
各 $(a,b)$ に対して、一日を終了したときにmoritaoy君が $(a,b)$ にいるような予定全ての、一日に休憩する時間の総和を求めてください。
ただし、二つの予定が異なるとは、二つの予定の一日に移動する回数が異なる、またはある $i$ があって $i$ 回目の移動に用いるベクトルが異なることをいいます。

Input

入力は以下の形式で与えられる。

$H$ $W$ $K$
$T_{(0,0)}$ $\ldots$ $T_{(0,2^W-1)}$
$\vdots$
$T_{(2^H-1,0)}$ $\ldots$ $T_{(2^H-1,2^W-1)}$
$G_{(0,0)}$ $\ldots$ $G_{(0,2^W-1)}$
$\vdots$
$G_{(2^H-1,0)}$ $\ldots$ $G_{(2^H-1,2^W-1)}$

$T_{(i,j)}$ が $-1$ でないとき、かつそのときに限り、moritaoy君はベクトル $(i,j)$ を持つ。
$2^H \leq i$ または $2^W \leq j$ ならばmoritaoy君はベクトル $(i,j)$ を持たない。

Constraints

入力は以下の条件を満たす。

• $0 \leq H,W \leq 9$
• $1 \leq K \leq 10^{5}$
• $-1 \leq T_{(i,j)} \lt 998244353$
• $-1 \leq G_{(i,j)} \lt 998244353$
• $T_{(i,j)}=-1$ のとき、かつそのときに限り、$G_{(i,j)}=-1$
• 入力は全て整数である

Output

出力は $2^H$ 行からなる。
$i$ 行目には $2^W$ 個の要素を空白区切りで出力する。
$i$ 行目の $j$ 番目の要素は、一日を終了したときにmoritaoy君が $(i-1,j-1)$ にいるような予定全ての、一日に休憩する時間の総和である。
ただし、答えは非常に大きくなることがあるので、$998244353$ で割ったあまりを出力すること。

Sample Input 1

0 0 10
1
2

Sample Output 1

440

Sample Input 2

1 2 2
1 2 3 4
5 6 7 0
9 8 7 6
1 3 3 3

Sample Output 2

355 358 363 386
391 408 419 378

Sample Input 3

1 1 100000
900000000 -1
-1 902010312
218738721 -1
-1 281371299

Sample Output 3

311157817 0
0 640524124