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

blank = [i for i in range(64)]
nump = int(sys.stdin.readline())
qpos = []
for _ in range(nump):
    j, i = map(int, sys.stdin.readline().split())
    qpos.append([j*8+i, j-i, j+i])
    for x in range(8):
        if j*8+x in blank: blank.remove(j*8+x)
        if x*8+i in blank: blank.remove(x*8+i)
        if 8*(j-i+x)+x in blank: blank.remove(8*(j-i+x)+x)
        if 8*(j+i-x)+x in blank: blank.remove(8*(j+i-x)+x)

idx = [0] * (8-nump)
used = [False] * len(blank)

def combination(n, k, m=0):
  if m==k:
    board = ['.'] * 64
    for qp, _, _ in qpos:  board[qp] = 'Q'
    for i in range(8):  print(''.join(board[i*8:i*8+8]))
  else:
    for i in range(n):
      if m>0 and idx[m-1]<i:  continue
      if used[i]: continue
      idx[m] = i
      q = blank[i]

      x,y = q%8, q//8
      for p, b, c in qpos:
          if x==p%8 or y==p//8: break
          if y==x+b or y==-x+c: break
      else:
          used[i]=True
          qpos.append([q, y-x, y+x])
          combination(n, k, m+1)
          qpos.pop()
          used[i]=False


combination(len(blank), 8-nump)
