/ 
実行時間制限: 3 sec / メモリ制限: 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
- 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する。
Problem Statement
Takahashi loves three integers B_1, B_2, and B_3.
He will write integers in an N \times N grid so that it will contain many vertical or horizontal contiguous segments whose sums are his favorite numbers.
For example, if he writes numbers as follows and his favorite number is 13, the segments painted red have the desired sum.
Let A_1, A_2, A_3 be the number of vertical or horizontal segments whose sums are B_1, B_2, B_3, respectively. He will then get A_1 \times B_1 + A_2 \times B_2 + A_3 \times B_3 points.
However, there are some limitations to what Takahashi can write in the grid. On each square, he must write a number between the lower and upper limits specified for that square.
On the square at the i-th row from the top and j-th column from the left, he must write a number between l_{i,j} and r_{i,j} (inclusive).
Find a way to write numbers so that Takahashi gets as many points as possible.
This is a so-called "marathon" problem where you are not assumed to find the optimal solution. Any valid solution will get a score.
Constraints
- N = 30
- 10 \leq B_1 \leq 19
- 20 \leq B_1 \leq 29
- 30 \leq B_1 \leq 39
- 1 \leq l_{i,j} \leq r_{i,j} \leq 9
Input
Input is given from Standard Input in the following format:
N B_1 B_2 B_3
l_{1,1} l_{1,2} \ldots l_{1,N}
l_{2,1} l_{2,2} \ldots l_{2,N}
:
l_{N,1} l_{N,2} \ldots l_{N,N}
r_{1,1} r_{1,2} \ldots r_{1,N}
r_{2,1} r_{2,2} \ldots r_{2,N}
:
r_{N,1} r_{N,2} \ldots r_{N,N}
Output
Let A_{i,j} be the number to write the square at the i-th row and j-th column. Print your solution in the following format:
A_{1,1} A_{1,2} \ldots A_{1,N}
A_{2,1} A_{2,2} \ldots A_{2,N}
:
A_{N,1} A_{N,2} \ldots A_{N,N}
Your solution will be considered valid if l_{i,j} \leq A_{i,j} \leq r_{i,j} for every A_{i,j}, and will get a score according to the Problem Statement.
If your output is not considered a valid solution, it will get 0 points in almost all test cases.
Input Generation
- B will be generated uniformly at random within the range specified in Constraints.
- l_{i,j} and r_{i,j} will be generated uniformly at random between 1 and 9 (inclusive), independently for each square. If l_{i,j} gets greater than r_{i,j}, they will be swapped.