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...
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


k = int(input())
pos = []
for i in range(k):
    x, y = map(int, input().split())
    pos.append((x, y))

N = 8
p = [i for i in range(N)]

def check(qs):
    board = [[0] * 8 for _ in range(8)]
    for q in qs:
        x, y = q
        board[x][y] = 1
    dirs = [(1, 1), (-1, -1), (1, -1), (-1, 1)]
    for q in qs:
        for d in dirs:
            dx, dy = q
            dx += d[0]
            dy += d[1]
            while (dx >= 0 and dy >= 0) and (dx < 8 and dy < 8):
                if board[dx][dy] == 1:
                    return False
                dx += d[0]
                dy += d[1]
    for i in range(8):
        for j in range(8):
            if board[i][j]:
                print("Q", end="")
            else:
                print(".", end="")
        print()
    return True

def perm(start):
    if start == N:
        qs = set((i, p[i]) for i in range(N))
        for x in pos:
            if not x in qs:
                break
        else:
            check(qs)
        return
    
    for i in range(start, N):
        p[i], p[start] = p[start], p[i]
        perm(start + 1)
        p[i], p[start] = p[start], p[i]

perm(0)






