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


def check(queen):
    for r1, c1 in queen:
        if not all((r1 == r2 and c1 == c2) or (r1 + c1 != r2 + c2 and r1 - c1 != r2 - c2) for r2, c2 in queen):
            return False
    return True


N = int(input())

# 0～7のリストを作成する
R = list(range(8))
C = list(range(8))

# R,Cから既にクイーンが置いてあるマス目を削除する
queen = []
for _ in range(N):
    r, c = map(int, input().split())
    queen.append((r, c))
    R.remove(r)
    C.remove(c)

# Rの全ての順列を作成する
for columns in permutations(C):
    # tmp_queenに8個のクイーンの位置を格納する
    tmp_queen = queen[:]
    for r, c in zip(R, columns):
        tmp_queen.append((r, c))
    for r1, c1 in tmp_queen:
        for r2, c2 in tmp_queen:
            if r1 == r2 and c1 == c2:
                continue
            else:
                if r1 == r2 or c1 == c2:
                    break
                if r1 + c1 == r2 + c2 or r1 - c1 == r2 - c2:
                    break
        else:
            continue
        break
    else:
        board = [''.join('Q' if (r, c) in tmp_queen else '.' for c in range(8))
                 for r in range(8)]
        print(*board, sep='\n')
        exit(0)

