AT_tenka1_2014_qualB_c 天下一王国の歴史

[problemUrl]: https://atcoder.jp/contests/tenka1-2014-qualb/tasks/tenka1_2014_qualB_c 天下一王国の歴史を学んでいるトモアキ君は、王国を導いた偉大な英雄である HAGIXILE について調べています。 HAGIXILE は奇行で知られる人物でした。彼は王国の領土を $ N\ \times\ N $ のマスに分割された盤面とし、白マスと黒マスに分けて扱いました。 白マスはその年に巡遊する地域、黒マスはその年に巡遊しない地域を意味したそうです。 マスの色は年ごとに変化しました。色は前年の盤面のマスの色を元に塗り替えられます。 あるマスの上下左右に隣接するマスのうち、塗り替え前に黒だったマスの個数が偶数なら、塗り替え後のそのマスは白マス、奇数なら黒マスになります。 四隅のマスに隣接するマスは 2 つ、端のマス (四隅のマスを除く) に隣接するマスは 3 つ、端以外のマスに隣接するマスは 4 つあります。 例えば、白マスを $ . $ で、黒マスを $ # $ で表すとして、ある年の盤面が以下だった場合、 ```

.#.
.##
.#.
```

翌年は以下のように塗り替えられます。

 ```
##.
###
##.
```

トモアキ君は、知られている最古の盤面が歴史書に載っているのを見付け、その盤面の塗り替え前の盤面を復元することを思い付きました。

最古の盤面が与えられるので、塗り替え前の盤面としてありうるものを $ 1 $ つ答えてください。ただし、そのような塗り替え前の盤面は必ず $ 1 $ つ以上存在するものとします。
                            

入力は以下の形式で標準入力から与えられる。 > $ N $ $ C1,1C1,2..C1,N $ $ C2,1C2,2..C2,N $ : $ CN,1CN,2..CN,N $ - $ 1 $ 行目には、列数と行数を表す整数 $ N\ (1\ \leq\ N\ \leq\ 750) $ が与えられる。 - $ 2 $ 行目から $ N $ 行は、$ i $ 行目 $ j $ 列目のマスの色 $ Ci,j\ (1\ \leq\ i,\ j\ \leq\ N) $ が与えられる。 - 白マスを $ . $ として表現し、黒マスを $ # $ として表現するものとする。 - 与えられる盤面には、少なくとも $ 1 $ つの塗り替え前の盤面がありうる。

与えられた盤面の塗り替え前の色を $ 1 $ 行に $ N $ 文字ずつ $ N $ 行で出力せよ。出力の末尾には改行をいれること。

### 部分点 - $ 1\ \leq{}\ N\ \leq{}\ 3 $ のケースに正解した場合、部分点として25点を与える。 - $ 1\ \leq{}\ N\ \leq{}\ 9 $ のケースに正解した場合、部分点としてさらに30点を与える。 ### Sample Explanation 1 出力の盤面の $ 1 $ 行 $ 1 $ 列目のマスについて、上にマスはありません。左にもマスはありません。右のマスは $ # $ です。 下のマスは $ . $ です。$ 1 $ 行 $ 1 $ 列目のマスの上下左右のマスで、$ # $ マスの個数が $ 1 $ となり、奇数なので塗り替え後の色は $ # $ です。 同様に、出力の盤面の $ 1 $ 行 $ 2 $ 列目のマスについて、上にマスはありません。左のマスは $ . $ です。 下のマスは $ # $ です。 右のマスは $ . $ です。 $ # $ マスの個数が $ 1 $ となり、奇数なので塗り替え後の色は $ # $ です。 また同様に、出力の盤面の $ 1 $ 行 $ 3 $ 列目のマスについて、上にマスはありません。左のマスは $ # $ です。下のマスは $ # $ です。右のマスはありません。$ # $ マスの個数が $ 2 $ となり、偶数なので塗り替え後の色は $ . $ です。 すべてのマスに対してこのような塗り替えを行うと、入力の盤面と一致するため正解です。