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...


N = 8
FREE = -1
NOT_FREE = 1


def printBoard():
    for i in range(N):
        for j in range(N):
            if X[i][j]:
                if not Y[i][j]:
                    return
    for i in range(N):
        for j in range(N):
            if Y[i][j]:
                print("Q", end = "")
            else:
                print(".", end = "")
        print("")

def recursive(i):
    if i == N:
        printBoard()
        return 

    for j in range(N):
        if col[j] == NOT_FREE or dpos[i + j] == NOT_FREE or dneg[i-j + N -1] == NOT_FREE:
            continue
        row[i] = NOT_FREE
        col[j] = NOT_FREE
        dpos[i + j] = NOT_FREE
        dneg[i-j + N -1] = NOT_FREE
        Y[i][j] = True
        
            
        recursive(i + 1)
        
        row[i] = FREE
        col[j] = FREE
        dpos[i + j] = FREE
        dneg[i-j + N -1] = FREE
        Y[i][j] = False

row = [FREE] * N
col = [FREE] * N
dpos = [FREE] * (2 * N - 1)
dneg = [FREE] * (2 * N - 1)
X = [[False for i in range(N)] for j in range(N)]
Y = [[False for i in range(N)] for j in range(N)]

n = int(input())
for i in range(n):
    nums=list(map(int,input().split()))
    X[nums[0]][nums[1]] = True



recursive(0)







