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...
# 17
# ALDS_13_A-8 クイーン問題

import itertools
import copy

k = int(input())
q_l = [[int(x) for x in input().split()] for y in range(k)]

x_l = list(range(8))
y_l = list(range(8))
plus_l = []
minus_l = []
for i in range(k):
    x_l.remove(q_l[i][1])
    y_l.remove(q_l[i][0])
    plus_l.append(q_l[i][0] + q_l[i][1])
    minus_l.append(q_l[i][0] - q_l[i][1])
    
per = itertools.permutations(x_l)
per2 = itertools.permutations(x_l)

for order in per:
    _p_l = copy.deepcopy(plus_l)
    _m_l = copy.deepcopy(minus_l)
    _x_l = list(order)
    for i,_y in enumerate(y_l):
        _p_l.append(_y + _x_l[i])
        _m_l.append(_y - _x_l[i])
    if len(set(_p_l)) == 8 and len(set(_m_l)) == 8:
        ans_l = [["."]*8 for j in range(8)]
        for j in range(k):
            ans_l[q_l[j][0]][q_l[j][1]] = "Q"
        for j in range(8-k):
            ans_l[y_l[j]][_x_l[j]] = "Q"
        for j in range(8):
            print(*(ans_l[j]), sep="")
