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...
def place(board, x, y, num, answer):
    width = len(board[0])
    r_dx = (x + 1) % width
    r_dy = (y + 1) % width
    for i in range(width - 1):
        board[y][(x + i + 1) % width] += num
        board[(y + i + 1) % width][x] += num
    div = [1,1,-1,-1]
    for i in range(4):
        x_i = div[(0 + i) % 4]
        y_i = div[(1 + i) % 4]
        l_dx = x + x_i
        l_dy = y + y_i
        while l_dx >= 0 and l_dy >= 0 and l_dx < width and l_dy < width:
            board[l_dy][l_dx] += num
            l_dx += x_i
            l_dy += y_i
    board[y][x] += num
    if num == 1:
        answer[y][x] = "Q"
    else:
        answer[y][x] = "."

def track(placed_num, board, answer):
    width = len(board)
    if placed_num == width:
        return True
    for x in range(width):
        for y in range(width):
            if not board[y][x]:
                place(board, x, y, 1, answer)
                if track(placed_num + 1, board, answer):
                    return True
                place(board, x, y, -1, answer)
    return False

board = [[0 for n in range(8)] for m in range(8)]
answer = [["." for n in range(8)] for m in range(8)]
placed_num = int(input())
for _ in range(placed_num):
    y, x = (int(n) for n in input().split(" "))
    place(board, x, y, 1, answer)
track(placed_num, board, answer)
for i in range(8):
    print("".join(answer[i]))