Goal
The Eight Queens Puzzle is a chess puzzle, where the goal is to arrange 8 queens on a standard 8x8 Chess board such that no queen threatens another one by standard Chess rules (i.e. no two queens may be in the same row, column, or diagonal).
You'll be given a Chess board where some of the queens are already placed. Your task is then to place the remaining queens, finishing the puzzle.
Input
8 lines: 8 characters, either a . indicating a free square, or a Q indicating a queen.
Output
The final board in the same format (8 lines of 8 characters).
Constraints
There's only one solution each time.
Example
Input
Q.......
........
...Q....
........
.......Q
.Q......
........
........
Output
Q.......
......Q.
...Q....
.....Q..
.......Q
.Q......
....Q...
..Q.....
