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...
N = 8
board = [['.'] * N for i in range(N)]
k = int(input())
for i in range(k):
    pos = list(map(int, input().split()))
    board[pos[0]][pos[1]] = 'Q'


def is_safe(board, row, col):
    for i in range(N):
        if board[row][i] == 'Q':
            return False

    for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
        if board[i][j] == 'Q':
            return False

    for i, j in zip(range(row, -1, -1), range(col, N, 1)):
        if board[i][j] == 'Q':
            return False

    for i, j in zip(range(row, N, 1), range(col, -1, -1)):
        if board[i][j] == 'Q':
            return False
    
    for i, j in zip(range(row, N, 1), range(col, N, 1)):
        if board[i][j] == 'Q':
            return False

    return True

def solve(board, col):
    if col >= N:
        return True

    for i in range(N):
        if board[i][col] == 'Q':
            return solve(board, col + 1)
        
    for i in range(N):
        if is_safe(board, i, col):
            board[i][col] = 'Q'
            if solve(board, col + 1):
                return True
            board[i][col] = '.'

    return False


solve(board, 0)
for i in range(N):
    print(''.join(board[i]))

