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...
queenExists = [[False] * 8 for _ in range(8)]

n = int(input())
for _ in range(n):
    x, y = map(int, input().split())
    queenExists[y][x] = True


def dfs(queenExists, c):
    if c >= 8:
        return True

    # check if queen exists in column c
    isQueen = False
    for r in range(8):
        if queenExists[r][c] is True:
            isQueen = True
    if isQueen is True:
        return dfs(queenExists, c + 1)

    for r in range(8):

        # check if queen can be put on [r][c]
        checkOk = True
        # check horizon
        for i in range(8):
            if queenExists[r][i] is True:
                checkOk = False
                break
        # check diagonal
        d = [[1, 1], [1, -1], [-1, 1], [-1, -1]]
        for dx, dy in d:
            n_r, n_c = r + dy, c + dx
            while 0 <= n_r < 8 and 0 <= n_c < 8:
                if queenExists[n_r][n_c] is True:
                    checkOk = False
                    break
                n_r, n_c = n_r + dy, n_c + dx
        if checkOk is False:
            continue

        # now that we can put queen on [r][c]
        queenExists[r][c] = True
        if dfs(queenExists, c + 1):
            return True
        queenExists[r][c] = False


dfs(queenExists, 0)

for i in range(8):
    for j in range(8):
        if queenExists[j][i] is True:
            print("Q", end="")
        else:
            print(".", end="")
    print()

