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 copy
import itertools

k=int(input())
pos = [['.' for _ in range(8)] for _ in range(8)]
rows = [i for i in range(8)]
cols = [i for i in range(8)]

for _ in range(k):
    r,c = map(int, input().split())
    pos[r][c] = 'Q'
    rows.remove(r)
    cols.remove(c)

for c in itertools.permutations(cols):
# for c in [(6,0,7,5,1,4)]:
    temp_pos = copy.deepcopy(pos)
    
    for r_i, c_i in zip(rows, c):
        temp_pos[r_i][c_i] = 'Q'
        
    flg = True
    
    for r_i in range(8):
        for c_i in range(8):
            
            if temp_pos[r_i][c_i]=='Q':
                
                next_r,next_c = r_i,c_i
                while 0<=next_r+1<=7 and 0<=next_c+1<=7:
                    next_r+=1
                    next_c+=1
                    if temp_pos[next_r][next_c]=='Q':
                        flg = False
                        break
                    
                next_r,next_c = r_i,c_i
                while 0<=next_r-1<=7 and 0<=next_c+1<=7:
                    next_r-=1
                    next_c+=1
                    if temp_pos[next_r][next_c]=='Q':
                        flg = False
                        break
                
                next_r,next_c = r_i,c_i
                while 0<=next_r-1<=7 and 0<=next_c-1<=7:
                    next_r-=1
                    next_c-=1
                    if temp_pos[next_r][next_c]=='Q':
                        flg = False
                        break
                
                next_r,next_c = r_i,c_i
                while 0<=next_r+1<=7 and 0<=next_c-1<=7:
                    next_r+=1
                    next_c-=1
                    if temp_pos[next_r][next_c]=='Q':
                        flg = False
                        break
                        
            if not flg:
                break
        if not flg:
            break
    if flg:
        break

if flg:
    for rows in temp_pos:
        print(*rows, sep='')
