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>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i < (n); ++i)
using namespace std;
typedef long long ll;
const int dx[] = {1, 1, -1, -1};
const int dy[] = {-1, 1, 1, -1};

bool check(vector<int> loc){
    rep(i, 8){
        int x = loc[i];
        int y = i;
        rep(dir, 4){
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            while(0<=nx && nx<8 && 0<=ny && ny<8){
                
                if(loc[ny] == nx) return false;

                nx += dx[dir];
                ny += dy[dir];
            }
        }
    }

    return true;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int k;
    cin >> k;

    vector<int> r(k), c(k);
    rep(i, k) cin >> r[i] >> c[i];

    vector<int> loc(8);
    rep(i, 8) loc[i] = i;

    do{
        bool verified = true;
        rep(i, k){
            if(loc[r[i]] != c[i]) verified = false;
        }
        if(!verified) continue;

        if(check(loc)) break;


    } while(next_permutation(loc.begin(), loc.end()));

    rep(i, 8){
        rep(j, 8){
            if(loc[i] == j) cout << 'Q';
            else cout << '.';
        }
        cout << endl;
    }

    return 0;
}
