A - マス目に数を書き込む問題

Time Limit: 3 sec / Memory Limit: 1024 MB

問題文

高橋君は、 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
  • 10B_119
  • 20B_229
  • 30B_339
  • 1l_{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する。