問題文

高橋君は、 $3$ つの整数 $B_1, B_2, B_3$ が好きです。

そこで、高橋君は、 $N×N$ のマス目に数を書き込み、縦または横に連続した数の区間で、和が好きな数になるものを、たくさん作ろうと思いました。

例えば、以下のようにマス目に数を書き込み、好きな整数が $13$ だった時、赤で塗ったような区間が、条件を満たす区間となります。

和が $B_1, B_2, B_3$ となる縦または横の区間の数を $A_1, A_2, A_3$ とすると、$A_1×B_1+A_2×B_2+A_3×B_3$ が、得られる点数となります。

ただし、高橋君は、盤面に自由に数を書き込むことが出来ません。各マスには、書き込める数の最小値と最大値が決められています。

上から $i$ 番目、左から $j$ 番目のマスには、$l_{i,j}$ から $r_{i,j}$ の間の数しか書き込むことが出来ません。

高橋君が獲得できる点数が、出来るだけ多くなるような、数の書き込み方を求めてください。

この問題は、最適な解を発見することを想定されていない、所謂マラソン系問題です。条件を満たす解であれば、点数を獲得することが出来ます。

制約

• $N = 30$
• $10$ ≦ $B_1$ ≦ $19$
• $20$ ≦ $B_2$ ≦ $29$
• $30$ ≦ $B_3$ ≦ $39$
• $1$ ≦ $l_{i,j}$ ≦ $r_{i,j}$ ≦ $9$

入力

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

$N$ $B_1$ $B_2$ $B_3$ $l_{1,1}$ $l_{1,2}$ ... $l_{1,N}$ $l_{2,1}$ $l_{2,2}$ ... $l_{2,N}$ : $l_{N,1}$ $l_{N,2}$ ... $l_{N,N}$ $r_{1,1}$ $r_{1,2}$ ... $r_{1,N}$ $r_{2,1}$ $r_{2,2}$ ... $r_{2,N}$ : $r_{N,1}$ $r_{N,2}$ ... $r_{N,N}$

出力

$i$ 行目、 $j$ 列目のマスに書き込む数を $A_{i,j}$ として、以下のフォーマットで出力せよ。

$A_{1,1}$ $A_{1,2}$ ... $A_{1,N}$ $A_{2,1}$ $A_{2,2}$ ... $A_{2,N}$ : $A_{N,1}$ $A_{N,2}$ ... $A_{N,N}$

出力された全ての $A_{i,j}$ について、$l_{i,j} ≦ A_{i,j} ≦ r_{i,j}$ が満たされていれば、正解となり、問題文に書かれた点数が得られる。

不正解となる出力が行われた場合は、ほぼ全てのテストケースが $0$ 点として扱われる。

入力生成方法

• $B$ は、制約の範囲内で一様なランダムで生成される。
• $l_{i,j}, r_{i,j}$ は、$1$ から $9$ の間で一様なランダムで独立に生成される。この際、$l_{i,j}$ が $r_{i,j}$ より大きかった場合、それらの値をswapする。

入出力例その他

入出力(Example01~03)、入出力検証プログラム（C++）のダウンロードはこちらから。