题目描述

高桥君喜欢玩解密。今天，他挑战了八皇后问题。八皇后问题就是在8×8的棋盘上放置8个皇后，使得横、纵、斜45度方向的同一直线上不能有两个或以上的皇后存在。

高桥君已经放置了3个皇后，但是他对于接下来如何放置毫无头绪。请你求出含有剩下五个皇后的八皇后的位置。

输入

输入为以下形式。

• 从第一行开始的8行每行给定一个含8个字符的字符串。
• 从第i行的开头开始第j个字符($c_{ij}$）表示第i行第j列是否放置了皇后。
• $c_{ij}$只会为''Q''或''.''。''.''表示此处没有放置皇后，''Q''表示此处放置了皇后。

输出

将放置了8个皇后的最终状态按输入的同样形式输出。

如果无解，则输出一行No Answer。

输入输出样例

样例1输入：

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

样例1输出：

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

样例2输入

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

样例2输出

No Answer

样例解释

• 在样例2中，开始时给定的1行与6行的皇后在斜45度的同一直线上。这种情况下满足条件的答案不存在。

感谢@hy1004 提供的翻译