問題文

HHWW のマス目があり、マス (i,j)(i,j) には22つの整数 Ai,j,Bi,jA_{i,j}, B_{i,j} が設定されています。

Ai,jA_{i,j} 点を消費してをマス (i,j)(i,j) を塗ることができ、色が塗られたマスについての(四方)連結成分ごとに、成分内のマスの Bi,jB_{i,j} の総和の絶対値の点を得ます。 また、すべてのマスが塗られている行や列11つにつき CC 点を得ます。

得点が最大になるような色の塗り方を11つ出力してください。

制約

  • 1H,W201\leq H, W\leq 20
  • 1Ai,j1061\leq A_{i,j}\leq 10^6
  • 106Bi,j106-10^6\leq B_{i,j}\leq 10^6
  • 1C1061\leq C \leq 10^6

入力

入力はすべて整数である。

H W CH\ W\ C
A1,1 A1,2  A1,WA_{1,1}\ A_{1,2}\ \dots\ A_{1,W}
A2,1 A2,2  A2,WA_{2,1}\ A_{2,2}\ \dots\ A_{2,W}
\vdots
AH,1 AH,2  AH,WA_{H,1}\ A_{H,2}\ \dots\ A_{H,W}
B1,1 B1,2  B1,WB_{1,1}\ B_{1,2}\ \dots\ B_{1,W}
B2,1 B2,2  B2,WB_{2,1}\ B_{2,2}\ \dots\ B_{2,W}
\vdots
BH,1 BH,2  BH,WB_{H,1}\ B_{H,2}\ \dots\ B_{H,W}

出力

色が塗られたマスを#、色が塗られていないマスを.として得点が最大となるようなマス目の塗り方を出力せよ。

サンプル

入力1
2 2 1
0 0
0 0
2 -2
-2 2
出力1
##
.#

(1,1)(1,1),(1,2)(1,2),(2,2)(2,2)を塗ります。連結成分は11つあり、11行目と22列目のマスがすべて塗られているため、A1,1A1,2A2,2+B1,1+B1,2+B2,2+C×2=4- A_{1,1} - A_{1,2} - A_{2,2} + |B_{1,1} + B_{1,2} + B_{2,2}| + C \times 2 = 4 であり、これが最大です。

以下の塗り方も得点が最大となるため正解となります。

.#
#.

連結成分は2つです。色の塗られたマスが上下左右に隣り合っていないため同じ連結成分には含まれません。

##
##

1,21,2 行目、1,21,2 列目が全て塗られているため C×4=4C\times 4=4 です。


入力2
3 3 4
6 5 7
4 9 4
5 2 7
-8 -1 -1
1 3 9
5 7 9
出力2
#..
..#
###

Submit


Go (1.21)