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...
#include"math.h"
#include <cstdio> 
#include <iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<string.h>
#include <sstream>  
#include <string>
//continue 只管for、while，不看if，不管多少if都直接无视,continue 表示终止本次（本轮）循环。当代码执行到continue时，本轮循环终止，进入下一轮循环，具有过滤功能。
using namespace std;
const int N = 8;
int row[N] = {0};
int col[N] = {0};
int dpos[2 * N - 1] = {0};
int dneg[2 * N - 1] = {0};
int X[N][N] = {0};
int num;
void printBoard(){
	for(int i = 0;i < N;i++){
		for(int j = 0;j < N;j++){
			if(X[i][j] && row[i] != j) return;
		}
	}
	for(int i = 0;i < N;i++){
		for(int j = 0;j < N;j++){
			if(row[i] == j) cout << 'Q';
			else cout << '.';
		}
		cout << endl;
	}
}
void recursive(int i){
	if(i == N){
		printBoard();
		return;
	}
	for(int j = 0;j < N;j++){
		if(col[j] || dpos[i + j] || dneg[i - j + (N - 1)]) continue;
		row[i] = j;
		col[j] = 1;
		dpos[i + j] = 1;
		dneg[i - j + (N - 1)] = 1;
		recursive(i + 1);
		row[i] = col[j] = dpos[i + j] = dneg[i - j + (N - 1)] = 0;
	}
}
int main(){
	int x,y;
	cin >> num;
	getchar();
	for(int i = 1;i<=num;i++){
		cin >> x >> y;
		getchar();
		X[x][y] = 1;
	}
	recursive(0);
}

