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...
# Heuristic Search - 8 Queens Problem
def reload_board(B,r,c,diff):
    # ?????¨???????????????????????????????????????????????????????????????????????????????????°????????????
    global Q,NUM
    for i in range(NUM):
        # ????¨???????????????¶???
        B[r][i] += diff
        B[i][c] += diff
        # ????§?45??????????????????????????¶???
        if i < r and c + (r-i) < NUM:
                B[i][c+(r-i)] += diff
        elif r <= i and c - (i-r) >= 0:
                B[i][c-(i-r)] += diff
        # ????§?135??????????????????????????¶???
        if i < r and c - (r-i) >= 0:
                B[i][c-(r-i)] += diff
        elif r <= i and c + (i-r) < NUM:
                B[i][c+(i-r)] += diff

def solve(queens, B, r):
    global NUM,SETROW
    if r >= NUM:
        return True
    if r in SETROW:
        return solve(queens,B,r+1)
    else:
        for c in range(NUM):
            if B[r][c] == 0:
                ifed = True
                queens[r] = c
                reload_board(B,r,c,1)
                if not solve(queens,B,r+1):
                    reload_board(B,r,c,-1)
                else:
                    return True
    return False

def print_board(queens):
    for i in range(NUM):
        for j in range(NUM):
            print('Q' if queens[i] == j else '.', end='')
        print()

NUM = 8
k = int(input())
B = [[0 for _ in range(NUM)] for _ in range(NUM)]
SETROW = []
queens = [-1 for _ in range(NUM)]
for _ in range(k):
    r,c = map(int, input().split())
    reload_board(B,r,c,1)
    SETROW.append(r)
    queens[r] = c

solve(queens,B,0)
print_board(queens)
