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>
#define int long long
using namespace std;

int A[8][8];

bool check(int y, int x){
  
  for(int dy=-1;dy<=1;dy++){
    
    for(int dx=-1;dx<=1;dx++){
      
      if( dy == 0 && dx == 0 ) continue;
      
      int ny = y, nx = x;      
      
      while(1){
	
	if( ny < 0 || nx < 0 || 8 <= ny || 8 <= nx ) break;
	
	if( A[ny][nx] != 0 ) return false;
	
	ny += dy;
	nx += dx;
	
      }
      
    }
    
  }
  
  return true;
}

void dfs(int y){
  
  if( y == 8 ){
    
    for(int i=0;i<8;i++){
      
      for(int j=0;j<8;j++){
	
	if( A[i][j] ) cout<<'Q';
	else cout<<'.';
	
      }
      
      cout<<endl;
      
    }
    
    exit(0);
  }
  
  int flg = 0;
    
  for(int j=0;j<8;j++){
    if( A[y][j] == 2 ) flg = 1;
  }
  
  if( !flg ){
    
    for(int j=0;j<8;j++){
      
      if( check( y, j ) == false ) continue;
      
      A[y][j] = 1;
      
      dfs( y + 1 );
      
      A[y][j] = 0;
      
    }
    
  }
  else dfs( y + 1 );
  
}

signed main(){
  
  int n;
  cin>>n;
  
  for(int i=0;i<n;i++){
    
    int y, x;
    cin>>y>>x;
    
    A[y][x] = 2;
    
  }
  
  dfs( 0 );
  
  return 0;
}

