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<bits/stdc++.h>
using namespace std;

#define ALL(x) (x).begin(), (x).end()

typedef struct{int x,y;}Point;
Point p1,p2;
int grid[8][8];
char ans[8][8];

bool Put(Point p){
	if(grid[p.y][p.x])return false;

	for(int dx=-1; dx<=1; dx++){
		for(int dy=-1; dy<=1; dy++){
			for(int d=0;d<8;d++){
				int nX=p.x+(d*dx), nY=p.y+(d*dy);
				if(nX<0||nY<0||nX>=8||nY>=8)continue;

				grid[nY][nX]=true;
			}
		}
	}
	return true;
}

int main(){
	int n;	cin>>n;
	vector<Point> init(n);
	for(int i=0;i<n;i++){
		cin>>init[i].y>>init[i].x;
	}

	for(int i=0;i<8;i++)for(int j=0;j<8;j++)ans[i][j]='.';
	vector<int> order(8);	for(int i=0;i<8;i++)order[i]=i;

	do{
		bool flag=true;
		for(int i=0;i<n;i++){
			if(order[init[i].y]!=init[i].x){
				flag=false;
				break;
			}
		}
		if(flag==false)continue;

		memset(grid,0,sizeof(grid));

		for(int i=0;i<8;i++){
			Point p;
			p.y=i;	p.x=order[i];
			if(Put(p)==false){
				flag=false;
				break;
			}
		}
		if(flag){
			for(int i=0;i<8;i++)ans[i][order[i]]='Q';

			for(int i=0;i<8;i++){
				for(int j=0;j<8;j++)cout<<ans[i][j];
				cout<<endl;
			}
			return 0;
		}
	}while(next_permutation(ALL(order)));

	return 0;
}

