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;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
const double PI = acos(-1);
const ll MOD = 1000000007;
using Graph = vector<vector<int>>;

void rec(int k,vector<pair<int, int>> &piece,vector<pair<int, int>> &queen) {
  if (k == 8) {
    rep(i,8) queen[i] = piece[i];
    return;
  }

  vector<vector<bool>> board(8, vector<bool>(8,true));

  rep(p,k) {
    rep(i,8) {
      rep(j,8) {
        if (i == piece[p].first) board[i][j] = false;
        if (j == piece[p].second) board[i][j] = false;
        if (i - j == piece[p].first - piece[p].second) board[i][j] = false;
        if (i + j == piece[p].first + piece[p].second) board[i][j] = false;
      }
    }
  }

  rep(i,8) {
    rep(j,8) {
      if (board[i][j]) {
        piece[k]= make_pair(i,j);
        rec(k+1, piece, queen);
      }
    }
  }

  return;
}

int main() {
  int k; cin >> k;
  vector<pair<int, int>> piece(8),queen(8);
  rep(i,k) {
    int r,c; cin >> r >> c;
    piece[i]= make_pair(r,c); 
  }

  rec(k,piece,queen);

  vector<vector<char>> ans(8, vector<char>(8,'.'));

  rep(i,8) ans[queen[i].first][queen[i].second] = 'Q';

  rep(i,8) {
    rep(j,8) cout << ans[i][j];
    cout << endl;
  }
}
