问题描述

高桥喜欢玩拼图游戏。今天，他想挑战八皇后问题。 八皇后问题是指在一个 $8×8$ 的国际象棋棋盘上，要求放置八个皇后，使得这八个皇后彼此之间不能相互攻击，即任意两个皇后不能处于同一行、同一列或同一斜线上。

图: 输出示例1的图形。每个皇后都位于垂直、水平和对角线上的45度直线上。

然而，当高桥放置了三个皇后之后，他就不知道如何继续放置剩下的五个皇后了。 请找到包括剩下的五个皇后在内的八个皇后的位置。

输入

输入数据按以下格式给出：$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' 表示已放置皇后。

输出

请按照输入数据的相同格式输出八个皇后完成放置后的状态。 如果不存在解，请输出 "No Answer"。

示例 1

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

输出示例 1

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

• 当按照上述位置放置皇后时，可以满足条件。

示例 2

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

输出示例 2

No Answer

• 在初始配置中，第1行和第6行的皇后已经在斜线上存在，因此不满足条件，答案不存在。

来源

ARC 001