問題文

高橋君は、パズルが好きです。今日は、$8$ クイーン問題に挑戦しようとしています。
$8$ クイーン問題とは、$8×8$ のチェスボード上の縦・横・斜め $45$ 度の同一直線状にそれぞれクイーンが $1$ つしか存在しないように、合計 $8$ つのクイーンを置く問題です。

図:出力例$1$の図。縦・横・斜め $45$ 度の同一直線状にそれぞれクイーンが $1$ つのみ存在する。

高橋君は、$3$ つのクイーンを置いたところで残りのクイーンをどう置いたら良いのか判らなくなってしまいました。
残りの $5$ つのクイーンを含めた $8$ つのクイーンの位置を求めなさい。

入力

入力は以下の形式で与えられる。$c_{11}$ $c_{12}$ … $c_{18}$ $c_{21}$ $c_{22}$ … $c_{28}$ : : $c_{81}$ $c_{82}$ … $c_{88}$

• $1$ 行目から $8$ 行目の各行は $8$ 文字の文字列が与えられる。
• $i$ 行目の先頭から $j$ 番目の文字である $c_{ij}$ は、$i$ 行目 $j$ 列目にクイーンが置かれているかどうかを表す。
• $c_{ij}$ は、'.' もしくは 'Q' で与えられ、'.' であればクイーンが置かれていないことを、'Q' であればクイーンが置かれていることを表す。

出力

$8$ つのクイーンを置き終わった後の状態のうちの $1$ つを、入力と同様のフォーマットで出力せよ。
答えが存在しない場合は、"No Answer" と $1$ 行で出力せよ。

入力例 1

........
........
.......Q
........
..Q.....
........
.Q......
........

出力例 1

Q.......
....Q...
.......Q
.....Q..
..Q.....
......Q.
.Q......
...Q....

• 上記のようにクイーンを置いた時、条件を満たすことが出来ます。

入力例 2

.....Q..
.Q......
........
........
........
Q.......
........
........

出力例 2

No Answer

• 初期配置で既に $1$ 行目と $6$ 行目のクイーンが斜め $45$ 度の同一直線状に存在するので、この地点で条件を満たしておらず答えは存在しません。

Source Name

ARC 001