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 <iostream>
#include <vector>
#include <algorithm>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;

int main(){
  int k;
  cin >> k;
  vector<int> r(k), c(k);
  vector< vector<bool> > board(8, vector<bool>(8, false));
  vector<int> x(8);
  vector<int> perm(8);
  rep(i, 8){
    x[i] = i;
    perm[i] = i;
  }
  rep(i, k){
    cin >> r[i] >> c[i];
    board[r[i]][c[i]] = true;
    x.erase(find(x.begin(), x.end(), r[i]));
    perm.erase(find(perm.begin(), perm.end(), c[i]));
  }
  do {
    vector<bool> check1(15, false);
    vector<bool> check2(15, false);
    rep(i, k){
      check1[r[i]+7-c[i]] = true;
      check2[r[i]+c[i]] = true;
    }
    bool flag = true;
    rep(i, 8-k){
      if (check1[x[i]+7-perm[i]] || check2[x[i]+perm[i]]){
        flag = false;
        break;
      }
      check1[x[i]+7-perm[i]] = true;
      check2[x[i]+perm[i]] = true;
    }
    if (flag){
      rep(i, 8-k){
        board[x[i]][perm[i]] = true;
      }
      break;
    }
  }while(next_permutation(perm.begin(), perm.end()));
  
  rep(i, 8){
    rep(j, 8){
      if (board[i][j])
        cout << 'Q';
      else
        cout << '.';
    }
    cout << endl;
  }
  
  return 0;
}
