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...
NOT_FREE = 1
FREE = 0
 
q = [0 for i in range(8)]
row = [0 for i in range(8)]
col = [0 for i in range(8)]
dneg = [0 for i in range (16)]
dpos = [0 for i in range (16)]
 
 
def printBord():
    for r in range(8):
        for c in range(8):
            if q[r] == c:
                print("Q",end="")
            else: print(".",end="")
        print()
 
 
def putQueen(i):
    if i == 8:
        printBord()
        return
     
    if row[i]:
        if putQueen(i+1):return
 
    for j in range(8):
        if (row[i] or col[j] or dpos[i+j] or dneg[i-j+7]) == NOT_FREE :continue
        q[i] = j
        col[j] = dpos[i+j] = dneg[i-j+7] = NOT_FREE
        if putQueen(i+1) : return
        col[j] = dpos[i+j] = dneg[i-j+7] = FREE
    return
 
 
if __name__=='__main__':
    k = int(input())
    for i in range(k):
        r, c = (int(x) for x in input().split())
        q[r] = c
        row[r] = col[c] = dpos[r+c] = dneg[r-c+7] = NOT_FREE
    putQueen(0)
