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 sys

def print_board(board):
    for y in xrange(8):
        for x in xrange(8):
            if x == board[y]:
                sys.stdout.write("Q")
            else:
                sys.stdout.write(".")
        print ""

# y = x - col + row
# y = - x + col + row

def check_threat(board, col, row):
    for y in xrange(8):
        if board[y] == col:
            return True

    for y in xrange(8):
        if board[y] < 0:
            continue

        is_on_line = (row - y == col - board[y])
        is_on_line = is_on_line or (row - y == -col + board[y])
        if is_on_line:
            return True

    return False

def can_place(pos, idx, col):
    for i in range(8):
        if pos[i] >= 0 and pos[i] == col: return True
    for i in range(8):
        if pos[i] >= 0 and abs(pos[i] - col) == abs(i - idx): return True
    return False


def place(board, row):
    if row == 8:
        print_board(board)
        return

    if board[row] >= 0:
        place(board, row + 1)
        return

    for i in xrange(8):
        if check_threat(board, i, row):
            continue

        board[row] = i
        place(board, row + 1)
        board[row] = -1


def solve():
    board = [-1 for i in xrange(8)]

    num_qs = int(raw_input())
    for _ in xrange(num_qs):
        x, y = map(int, raw_input().split())
        board[x] = y

    place(board, 0)


if __name__ == "__main__":
    solve()