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 # クイーンの数
n = int(input())

raw = [-1 for i in range(N)]
col = [0 for i in range(N)] # FREE: 0, NOT_FREE: 1
dpos = [0 for i in range(2*N-1)] # FREE: 0, NOT_FREE: 1
dneg = [0 for i in range(2*N-1)] # FREE: 0, NOT_FREE: 1


def put_queen(i):
	if i == N:
		return True
	elif raw[i] != -1:
		if put_queen(i+1):
			return True
		else :
			return False
	else:
		for j in range(N):
			if col[j] == 1 or dpos[i+j] == 1 or dneg[i-j+N-1] == 1:
				continue
			raw[i] = j
			col[j] = dpos[i+j] = dneg[i-j+N-1] = 1
			if put_queen(i+1):
				return True
			else :
				raw[i] = -1
				col[j] = dpos[i+j] = dneg[i-j+N-1] = 0
		return False


def output_result():
	for i in range(N):
		out_raw = ['.' for i in range(N)]
		out_raw[raw[i]] = 'Q'
		print(''.join(map(str, out_raw)))


for i in range(n):
	r, c = map(int, input().split())
	raw[r] = c
	col[c] = dpos[r+c] = dneg[r-c+N-1] = 1

put_queen(0)
output_result()
