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 sys

N = 8
row = [-1] * N
col = [0] * N
dpos = [0] * (N*2-1)
dneg = [0] * (N*2-1)


def print_board():
    for i in range(N):
        for j in range(N):
            if row[i] == j:
                print("Q", end='')
            else:
                print(".", end='')
        print("\n", end='')


def put_queen(i):
    if i == N:
        return True
    elif row[i] != -1:
        if put_queen(i+1):
            return True
        else:
            return False
    else:
        for j in range(N):
            if col[j] == 1 or dpos[i+j] == 1 or dneg[i-j+N-1] == 1:
                continue
            row[i] = j
            col[j] = dpos[i+j] = dneg[i-j+N-1] = 1
            if put_queen(i+1):
                return True
            else:
                row[i] = -1
                col[j] = dpos[i+j] = dneg[i-j+N-1] = 0
        return False


line = sys.stdin.readline()
n = int(line)
for i in range(n):
    line = sys.stdin.readline()
    r, c = map(int, line.split())
    row[r] = c
    col[c] = dpos[r+c] = dneg[r-c+N-1] = 1

put_queen(0)
print_board()

