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 FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   for(int i=0;i<(n);++i)
#define SORT(c)    sort((c).begin(),(c).end())
#define CLR(a)     memset((&a), 0 ,sizeof(a))//clear memory
#define dump(x)    cerr << #x << " = " << (x) << endl;//debug
#define debug(x)   cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define EPS        1e-10//sample:if((double)>=(double)+EPS)
//cin,cout release
//std::cin.tie(0);
//ios::sync_with_stdio(false);

using namespace std;

int row[8]={},col[8]={},lefta[15]={},righta[15]={};
bool X[8][8]={};
void p(){
  rep(i,8)rep(j,8)if(X[i][j]&&(row[i]!=j))return;
  rep(i,8){
    rep(j,8)cout<<(row[i]==j?"Q":".");
    cout<<endl;
  }
}
void dfs(int i){
  if(i==8){p();return;}
  rep(j,8){
    if(col[j]==1||lefta[i+j]==1||righta[i-j+7]==1)continue;
    row[i]=j;
    col[j]=lefta[i+j]=righta[i-j+7]=1;
    dfs(i+1);
    row[i]=col[j]=lefta[i+j]=righta[i-j+7]=0;
  }
}

int main(){
  int k,r,c;
  cin>>k;
  rep(i,k){
    cin>>r>>c;
    X[r][c]=1;
  }
  dfs(0);
  return 0;
}
