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;
int k;
int col[9];
int dpos[20];
int dneg[20];

int store[9];
bool book[9];

inline bool check(int i,int j) {
    if(col[j] == 1 || dpos[i + j] == 1 || dneg[i - j + 10] == 1) {
        return false;
    }
    return true;
}

void dfs(int row) {
    if(row == 9) {
        for (int i = 1; i <= 8; i++) {
            for(int j = 1; j <= 8; j++) {
                cout << ((store[i] == j) ? "Q" : "." );
            }
            cout << endl;
        }
        return ;
    }
    if(book[row]) {
        dfs(row + 1);
    }
    else {
        for (int i = 1; i <= 8; i++) {
            if (check(row,i)) {
                col[i] = dpos[row + i] = dneg[row - i + 10] = 1;
                store[row] = i;
                dfs(row + 1);
                col[i] = dpos[row + i] = dneg[row - i + 10] = 0;
            }
        }
    }

}

int main() {
    cin >> k;
    while (k--) {
        int x,y; cin >> x >> y;
        x++, y++;
        book[x] = 1;
        store[x] = y;
        col[y] = 1;
        dpos[x + y] = 1;
        dneg[x - y + 10] = 1;
    }
    dfs(1);
    return 0;
}

