0 atcoder#AGC004C. [AGC004C] AND Grid

[AGC004C] AND Grid

配点 : 700700

問題文

高橋君と青木君は、縦 HH マス、横 WW マスの透明な方眼紙を 11 枚ずつ手に入れました。

高橋君は、自分の方眼紙のいくつかのマスを赤く塗りました。 このとき、赤いマスは上下左右に連結でした。 つまり、どの赤いマスからどの赤いマスへも、上下左右に隣り合う赤いマスのみを辿って行き来できます。

また、青木君は、自分の方眼紙のいくつかのマスを青く塗りました。 このとき、青いマスは上下左右に連結でした。

その後、高橋君と青木君は、22 枚の方眼紙をそのままの向きでぴったりと重ねました。 すると、赤いマスと青いマスが重なるマスのみが紫色になって見えました。

紫色のマスの配置が、長方形に並ぶ文字 aija_{ij} (1iH1 \leq i \leq H1jW1 \leq j \leq W) として与えられます。 上から ii 行目、左から jj 列目のマスが紫色ならば、aija_{ij}# であり、紫色でなければ、aija_{ij}. です。 このとき、最も外側のマスは紫色でないことが保証されます。 つまり、i=1,Hi=1,H または j=1,Wj=1,W ならば、aija_{ij}. です。

問題文の条件を満たすような、赤いマスの配置と青いマスの配置のペアをひとつ求めてください。 解は必ず存在することが示せます。

制約

  • 3H,W5003 \leq H,W \leq 500
  • aija_{ij}# または . である。
  • i=1,Hi=1,H または j=1,Wj=1,W ならば、aija_{ij}. である。
  • aija_{ij} のうち少なくとも 11 つは # である。

入力

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

HH WW

a11a_{11}......a1Wa_{1W}

::

aH1a_{H1}......aHWa_{HW}

出力

問題文の条件を満たすような、赤いマスの配置と青いマスの配置のペアをひとつ出力せよ。

  • 11 行目から HH 行目までには、赤いマスの配置を出力せよ。
  • H+1H+1 行目には、空行を出力せよ。
  • H+2H+2 行目から 2H+12H+1 行目までには、青いマスの配置を出力せよ。

どちらも、紫色のマスの配置と同様のフォーマットで出力せよ。

5 5
.....
.#.#.
.....
.#.#.
.....
.....
#####
#....
#####
.....

.###.
.#.#.
.#.#.
.#.#.
.....

例えば、次のような赤いマスの配置と青いマスの配置のペアが考えられます。

7 13
.............
.###.###.###.
.#.#.#...#...
.###.#...#...
.#.#.#.#.#...
.#.#.###.###.
.............
.............
.###########.
.###.###.###.
.###.###.###.
.###.###.###.
.###.###.###.
.............

.............
.###.###.###.
.#.#.#...#...
.###.#...#...
.#.#.#.#.#...
.#.#########.
.............

例えば、次のような赤いマスの配置と青いマスの配置のペアが考えられます。