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

from collections import namedtuple

position = namedtuple("position","row column")
def input_queens():
    queens = []
    n = int(input())
    for _ in range(n):
        row,column = [int(x) for x in input().split()]
        queens.append(position(row,column))
    return queens

def output_board(queens):
    for r in range(8):
        for c in range(8):
            print("Q" if position(r,c) in queens else ".",end = "")
        print()

def atackable(p,queens):
    return(
        p.row in [q.row for q in queens]
        or p.column in [q.column for q in queens]
        or any([abs(p.row - q.row) == abs(p.column-q.column) for q in queens])
    )


def next_p(p):
    if p.column == 7:
        return position(p.row+1,0)
    else:
        return position(p.row,p.column+1)
def over(p):
    return p.row > 7
    
def all_queens(queens):
    def rec(p,queens):
        if len(queens) == 8:
            return queens
        elif over(p):
            return False
        elif atackable(p,queens):
            return rec(next_p(p),queens)
        else:
            result = rec(position(p.row+1,0),queens+[p])
            return result if result else rec(next_p(p),queens)
    return rec(position(0,0),queens)
    

queens = input_queens()
output_board(all_queens(queens))

