The goal of 8 Queens Problem is to put eight queens on a chess-board such that none of them threatens any of others. A queen threatens the squares in the same row, in the same column, or on the same diagonals as shown in the following figure.

<image>


For a given chess board where $k$ queens are already placed, find the solution of the 8 queens problem.

Constraints

* There is exactly one solution

Input

In the first line, an integer $k$ is given. In the following $k$ lines, each square where a queen is already placed is given by two integers $r$ and $c$. $r$ and $c$ respectively denotes the row number and the column number. The row/column numbers start with 0.

Output

Print a $8 \times 8$ chess board by strings where a square with a queen is represented by 'Q' and an empty square is represented by '.'.

Example

Input

2
2 2
5 3


Output

......Q.
Q.......
..Q.....
.......Q
.....Q..
...Q....
.Q......
....Q...
import copy
from typing import List, Tuple


def _fill_forbidden_pos(board: List[List[int]], pos: Tuple[int, int]) -> None:
    row, col = pos[0], pos[1]
    # Horizontal.
    for i in range(8):
        board[row][i] = 1
    # Vertical.
    for i in range(8):
        board[i][col] = 1
    # Diagonal.
    for i in range(min(row, col) + 1):
        board[row - i][col - i] = 1
    for i in range(min(7 - row, 7 - col) + 1):
        board[row + i][col + i] = 1
    for i in range(min(row, 7 - col) + 1):
        board[row - i][col + i] = 1
    for i in range(min(7 - row, col) + 1):
        board[row + i][col - i] = 1


def set_queens(board: List[List[int]], num_rest_q: int) -> bool:
    global queens_list
    if 0 == num_rest_q:
        return True
    board_copied = copy.deepcopy(board)
    for row in range(8):
        for col in range(8):
            if 1 != board_copied[row][col]:
                _fill_forbidden_pos(board_copied, (row, col))
                if set_queens(board_copied, num_rest_q - 1):
                    queens_list.append((row, col))
                    return True
                else:
                    board_copied = copy.deepcopy(board)
    return False


if __name__ == "__main__":
    board = [[0] * 8 for _ in range(8)]
    queens_list = []

    num_init_Q = int(input())
    for _ in range(num_init_Q):
        (row, col) = map(lambda x: int(x), input().split())
        queens_list.append((row, col))
        _fill_forbidden_pos(board, (row, col))

    num_rest_q = 8 - num_init_Q
    set_queens(board, num_rest_q)

    for q_pos in queens_list:
        board[q_pos[0]][q_pos[1]] = -1
    for one_row in board:
        print("".join(["Q" if -1 == pos else "." for pos in one_row]))

