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,s,e) for((i)=(s);(i)<(int)(e);(i)++)
#define REP(i,e) FOR(i,0,e)

#define all(o) (o).begin(), (o).end()
#define psb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))

typedef long long ll;
typedef pair<int, int> PII;

const double EPS = 1e-10;

const int N = 8;
int n;
int r[N], c[N], rdd[N*2-1], ldd[N*2-1];
int z[N][N];

void print_board() {
  int i, j;
  for (i=0; i<N; i++)
    for (j=0; j<N; j++) {
      if (z[i][j] && r[i]!=j) return; 
    }

  for (i=0; i<N; i++) {
    for (j=0; j<N; j++)
      printf("%c", (r[i]==j) ? 'Q' : '.');
    printf("\n");
  }
}

void rec(int i) {
  int j;
  if (i==N) {
    print_board();
    return;
  }

  for (j=0; j<N; j++) {
    if (c[j] || rdd[N-1+i-j] || ldd[i+j]) continue;
    r[i] = j;
    c[j] = rdd[N-1+i-j] = ldd[i+j] = 1;
    rec(i+1);
    r[i] = -1;
    c[j] = rdd[N-1+i-j] = ldd[i+j] = 0;
  }
}

int main() {
  int i, j;
  memset(r, 0xff, sizeof(r));
  memset(c, 0, sizeof(c));
  memset(rdd, 0, sizeof(rdd));
  memset(ldd, 0, sizeof(ldd));
  memset(z, 0, sizeof(z));
  scanf("%d ", &n);
  for (i=0; i<n; i++)
    for (j=0; j<n; j++) {
      int x, y;
      scanf("%d%d ", &y, &x);
      z[y][x] = 1; 
    }
  
  rec(0); 

	return 0;
}