Dessert Witch

Time Limit : 2 sec, Memory Limit : 35353 KB

問題文

お菓子の魔女 CHARLOTTE は巴マミとクッキーゲームを楽しんでいる.クッキーゲームは 8\times 8 の格子状に区切られたテーブルクロスの上にチーズクッキーとチョコレートクッキーを置いて行われる.各格子には高々 1 個のチョコレートクッキーまたはチーズクッキーしか置くことはできない.

お菓子の魔女はチーズクッキーを,巴マミはチョコレートクッキーを交互に置いてゲームを行う.自分のクッキーを置いたあと,そのクッキーから上下左右斜めの各 8 方向について,置くクッキーとすでに置いていた自分のクッキーの間に相手のクッキーのみが直線に並んでいた場合に,その挟まれた相手のクッキーのすべてが自分のクッキーで置き換えられる.クッキーゲームのプレイヤーは自分のターンが回ってきた時,1 つ自分のクッキーを置くことができる.ただし,相手のクッキーを少なくとも 1 つ以上自分のクッキーに置き換えられなければならない.そのような置き場がない場合,自分のターンをパスをしなければならない.

お菓子の魔女も巴マミも考えるのが少々苦手である.そこで,回ってきたターン毎にそのターンの中で置き換えられるクッキーの数を最大化することを考えることにした.巴マミのターンのときに置き換えられるクッキーの数を最大にするようなクッキーを置く場所の候補が複数ある場合は,より上の場所を,それでも複数ある場合はより左の場所を選択することにした.また同様に,お菓子の魔女のターンのときに候補が複数ある場合はより下の場所を,それでも複数ある場合はより右の場所を選択することにした.

テーブルクロスに置かれたクッキーの状態が与えられるので,巴マミからはじめ,彼女たちがそこからクッキーゲームを行い,共に新たなクッキーが置けなくなるまでゲームを続けた時のテーブルクロスの上に置かれたクッキーの状態を求めよ.

入力形式

入力は以下の形式で与えられる.


s_{11} s_{12} ... s_{18}\\
s_{21} s_{22} ... s_{28}\\
...\\
s_{81} s_{82} ... s_{88}\\

s_{ij} はテーブルクロスに置かれたクッキーの初期状態を表す文字で,上から i 行目,左から j 列目の格子の状態を表す.チョコレートクッキーが置かれているときs_{ij}'o' であり,チーズクッキーが置かれているときは 'x', 何も置かれていないときは '.' となる.

出力形式

クッキーゲームが行われた後のテーブルクロスの上に置かれたクッキーの状態を,入力形式と同じ形式で出力せよ.

制約

  • s_{ij}'o', 'x', '.' のいずれかである.

入出力例

入力例 1

ooox....
.x......
ooo.....
........
........
........
........
........

出力例1

ooooo...
.o......
ooo.....
...o....
....o...
........
........
........

入力例 2

........
........
........
...ox...
...xo...
........
........
........

出力例 2

xxxxxxxx
xxxooxxx
xxxxooxx
xxxxxxxx
ooxxooox
ooxoooox
oxooooox
ooooooox

入力例 3

........
........
..ooo...
..oxo...
..ooo...
........
........
........

出力例 3

........
........
..ooo...
..ooo...
..ooo...
.....o..
......o.
........

Problem Setter: Flat35

Source: ACM-ICPC Japan Alumni Group Summer Camp 2011 , Day 4, Tokyo, Japan, 2011-09-19
http://acm-icpc.aitea.net/