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;
using ll = long long;
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define debug(x) cerr << #x << ": " << x << endl;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

int main() {
    ll k;
    cin >> k;
    ll c[8];
    memset(c, -1, sizeof(c));
    rep(i, k) {
        ll x, y;
        cin >> x >> y;
        c[x] = y;
    }
    ll v[8];
    rep(i, 8) v[i] = i;

    vector<string> ans(8, "........");

    do {
        bool ok = true;
        rep(i, 8) {
            if (c[i] != -1 && v[i] != c[i]) ok = false;
            rep(j, 8) {
                if (i >= j) continue;
                if (c[j] != -1 && v[j] != c[j]) ok = false;
                if (abs(i - j) == abs(v[i] - v[j])) ok = false;
            }
        }
        if(ok) rep(i, 8) ans[i][v[i]] = 'Q';
    } while(next_permutation(v, v+8));

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