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


class EightQueen:
    NQUEENS = 8
    SIZE = 8

    class Board:
        def __init__(self, size):
            self.queens = []
            self.size = size

        def place(self, i, j):
            self.queens.append((i, j))

        def count(self):
            return len(self.queens)

        def ok(self, i, j):
            for qi, qj in self.queens:
                if qi == i:
                    return False
                if qj == j:
                    return False
                if i - j == qi - qj:
                    return False
                if i + j == qi + qj:
                    return False
            return True

        def __str__(self):
            result = []
            for i in range(self.size):
                s = ''
                for j in range(self.size):
                    if (i, j) in self.queens:
                        s += "Q"
                    else:
                        s += "."
                result.append(s)
            return '\n'.join(result)

    def __init__(self):
        self.board = self.Board(self.SIZE)

    def add_queen(self, i, j):
        self.board.place(i, j)

    def solve(self):
        def _solve(board, si, sj):
            if board.count() == self.NQUEENS:
                return board

            for i, j in _from_pos(si, sj):
                if board.ok(i, j):
                    b = deepcopy(board)
                    b.place(i, j)
                    result = _solve(b, i, j)
                    if result is not None:
                        return result
            else:
                return None

        def _from_pos(i, j):
            for n in range(i*self.SIZE + j, self.SIZE*self.SIZE):
                yield (n // self.SIZE, n % self.SIZE)

        self.board = _solve(self.board, 0, 0)

    def __str__(self):
        if self.board is None:
            return 'no solution'
        else:
            return str(self.board)


def run():
    n = int(input())
    q = EightQueen()

    for _ in range(n):
        i, j = [int(i) for i in input().split()]
        q.add_queen(i, j)

    q.solve()
    print(q)


if __name__ == '__main__':
    run()

