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;

int k;
vector<int> ax, ay;

void sol(vector<int> x, vector<int> y){
  if(ax.size()==8) return;
  
  if(x.size()==8){
    for(int i=0;i<8;i++){
      //cout<< x[i] << " " << y[i] <<endl;
      ax.push_back(x[i]);
      ay.push_back(y[i]);
    }
    //cout<< endl;
    return;
  }
    
  int flag=1, cle;
  for(int i=0;i<8;i++){
    for(int j=0;j<8;j++){
      cle=1;
      for(int k=0;k<x.size();k++){
        if(x[k]==i || y[k]==j || x[k]-i==y[k]-j || i+j==x[k]+y[k]){
          cle=0;
        }else{
          //cout<< i << " " << j << " " << x[k] << " " << y[k] <<endl;
        }
      }
      if(cle){
        x.push_back(i);
        y.push_back(j);
        sol(x, y);
    	x.pop_back();
    	y.pop_back();
      }
    }
  }
}

int main(){
  
  int r, c;
  vector<int> x, y;
  vector< vector<char> > v;
  cin >> k;
  
  for(int i=0;i<k;i++){
    cin>> r >> c;
    x.push_back(r);
    y.push_back(c);
  }
  
  sol(x, y);
  
  v.resize(8);
  for(int i=0;i<8;i++) v[i].resize(8, '.');
  for(int i=0;i<8;i++) v[ax[i]][ay[i]]='Q';
  
  for(int i=0;i<8;i++){
    for(int j=0;j<8;j++){
      cout<< v[i][j];
    }
    cout<< endl;
  }
  
  return 0;
}
