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 copy import deepcopy, copy
class QueenMAP():
    __slots__ = ["yoko", "tate", "naname1", "naname2", "MAP"]
    def __init__(self):
        self.yoko = set()
        self.tate = set()
        self.naname1 = set()
        self.naname2 = set()
        self.MAP = [["."] * 8 for _ in range(8)]
    def add(self, y, x):
        self.MAP[y][x] = "Q"
        self.yoko.add(y)
        self.tate.add(x)
        self.naname1.add(y - x)
        self.naname2.add(x + y)
    def check(self, y, x):
        if x in self.tate or (y - x) in self.naname1 or (x + y) in self.naname2:
            return False
        return True
    def allcheck(self):
        for i in range(8):
            if not "Q" in self.MAP[i]:
                return False
        return True
def MAIN():
    f = lambda M: "\n".join("".join(map(str, m)) for m in M)
    QM = QueenMAP()
    n = int(input())
    for _ in range(n):
        a, b = map(int, input().split())
        QM.add(a, b)
    dp = [(deepcopy(QM), n)]
    while dp:
        Q, cnt = dp.pop()
        if cnt == 8:
            if Q.allcheck():
                print(f(Q.MAP))
                break
            continue
        cnt += 1
        for i in range(8):
            if i in Q.yoko:
                continue
            for j in range(8):
                if Q.check(i, j):
                    CQ = deepcopy(Q)
                    CQ.add(i, j)
                    dp.append((CQ, cnt))
MAIN()

