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 <cstdio>
using namespace std;
bool flag = false;
void check(int table[8][8],int y,int x){
	int dx[]={0,0,1,1,1,-1,-1,-1};
	int dy[]={1,-1,0,1,-1,0,1,-1};
	for(int i=0;i<8;i++){
		int tmpx=x,tmpy=y;
		while(tmpx+dx[i]<8 && tmpx+dx[i]>=0 && tmpy+dy[i]<8 && tmpy+dy[i]>=0){
			table[tmpy+dy[i]][tmpx+dx[i]]=2;
			tmpy+=dy[i];
			tmpx+=dx[i];		
		}
	}
}
void dfs(int now,int table[8][8]){
	if(flag==true){
		return ;
	}else if(now==8){
		for(int i=0;i<8;i++){
			for(int k=0;k<8;k++){
				if(table[i][k]==1){
					printf("Q");
				}else{
					printf(".");
				}
			}
			printf("\n");
		}
		flag=true;
	}else{
		
		for(int i=0;i<8;i++){
			for(int k=0;k<8;k++){
				int tmptable[8][8]={0};
				for(int z=0;z<8;z++){
					for(int j=0;j<8;j++){
						tmptable[z][j]=table[z][j];
					}
				}
				if(tmptable[i][k]==0){
					tmptable[i][k]=1;
					check(tmptable,i,k);
					dfs(now+1,tmptable);
				}
			}
		}		
	}
}


int main(){
	int cases;
	int table[8][8]={0};
	// 0=can 1=queen 2=can't
	scanf("%d",&cases);
	int x,y;
	for(int i=0;i<cases;i++){
		scanf("%d%d",&y,&x);
		table[y][x]=1;
		check(table,y,x);
	}
	dfs(cases,table);
}
