問題文

縦 $H$ 横 $W$ のマス目があり、マス $(i,j)$ には$2$つの整数 $A_{i,j}, B_{i,j}$ が設定されています。

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

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

制約

• $1\leq H, W\leq 20$
• $1\leq A_{i,j}\leq 10^6$
• $-10^6\leq B_{i,j}\leq 10^6$
• $1\leq C \leq 10^6$

入力

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

出力

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

サンプル

2 2 1
0 0
0 0
2 -2
-2 2

##
.#

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

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

.#
#.

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

##
##

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

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

#..
..#
###