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>
#define N 8
using namespace std;
int usedcol[N], usedrow[N], usedlowl[2*N-1], usedlowr[2*N-1];
void rec(int cnt) {
  if (cnt == N) {
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < N; ++j)
	cout << (usedrow[i] == j ? 'Q' : '.');
      cout << endl;
    }
    return;
  }
  if (usedrow[cnt] != -1) rec(cnt + 1);
  else{
    for (int i = 0; i < N; ++i) {
      if (usedrow[cnt] == -1 && usedcol[i] == -1 && usedlowl[cnt + i] == -1 && usedlowr[N - 1 + cnt - i] == -1) {
	usedrow[cnt] = i;
	usedcol[i] = cnt;
	usedlowl[cnt + i] = usedlowr[N - 1 + cnt - i] = 1;
	rec(cnt + 1);
	usedrow[cnt] = usedcol[i] = usedlowl[cnt + i] = usedlowr[N - 1 + cnt - i] = -1;
      }
    }
  }
}
int main() {
  int n; cin >> n;
  for (int i = 0; i < N; ++i) usedrow[i] = usedcol[i] = -1;
  for (int i = 0; i < 2 * N - 1; ++i) usedlowl[i] = usedlowr[i] = -1;
  for (int i = 0; i < n; ++i) {
    int x, y; cin >> y >> x;
    usedrow[y] = x;
    usedcol[x] = y;
    usedlowl[x + y] = usedlowr[N - 1 + y - x] = 1;
  }
  rec(0);
  return 0;
}

