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=int(input())
L=[[0 for i in range(8)]for j in range(8)]

Q=[]

for i in range(N):
    h,w=map(int,input().split())
    Q.append((h,w))
    #L[h][w]="Q"
if N==8:
    L=[["." for i in range(8)]for j in range(8)]
    for q in Q:
        #print(q)
        L[q[0]][q[1]]="Q"
    for h in range(8):
        print("".join(L[h]))
    exit()
    
for i in range(len(Q)):
    H,W=Q[i]
    for j in range(1,8):
        if H+j>=8 or W+j>=8:
            break
        L[H+j][W+j]=1
    for j in range(1,8):
        if H+j>=8 or W-j<0:
            break
        L[H+j][W-j]=1
    for j in range(1,8):
        if W+j>=8 or H-j<0:
            break
        L[H-j][W+j]=1
    for j in range(1,8):
        if H-j<0 or W-j<0:
            break
        L[H-j][W-j]=1
    for j in range(1,8):
        if W+j>=8:
            break
        L[H][W+j]=1
    for j in range(1,8):
        if W-j<0:
            break
        L[H][W-j]=1
    for j in range(1,8):
        if H+j>=8:
            break
        L[H+j][W]=1
    for j in range(1,8):
        if H-j<0:
            break
        L[H-j][W]=1
for i in Q:
    L[i[0]][i[1]]="Q"
#print(L)
#for i in range(8):
    #print(L[i])
d=[]
for i in range(8):
    for j in range(8):
        if L[i][j]==0:
            d.append((i,j))

D=[{}for i in range(8)]
D[0][tuple(Q)]=d
#print(D)
import copy
for i in range(1,8-N):
    for k,v in D[i-1].items():
        K=list(k)
        for x in range(len(v)):
            l=[]
            for y in range(x+1,len(v)):
                if x==y:
                    continue
                if abs(v[x][0]-v[y][0])==abs(v[x][1]-v[y][1]) or (v[x][0]-v[y][0])*(v[x][1]-v[y][1])==0:
                    continue
                else:
                    l.append(v[y])
            #print(v[x][0],v[x][1])
            D[i][tuple(K+[v[x]])]=l
#print(D[8-N-1])
for k,v in D[8-N-1].items():
    if len(v)==1:
        
        for i in k:
            L[i[0]][i[1]]="Q"
        L[v[0][0]][v[0][1]]="Q"
        for h in range(8):
            for w in range(8):
                if L[h][w]!="Q":
                    L[h][w]="."
        for h in range(8):
            print("".join(L[h]))
        exit()
