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>
#include <vector>
#include <cmath>
#include <string>

// (x, y)と(sx, sy)が同一直線上にあるか判定
inline bool sameline(int x, int y, int sx, int sy) {
    return x == sx || y == sy || abs(x - sx) == abs(y - sy);
}

// x行目にクイーンを置く
bool dfs(std::vector<int>& queen, int x) {
    if (x == 8) return true;

    if (queen[x] >= 0) {
        for (int sx = 0; sx < x; ++sx) {
            if (sameline(x, queen[x], sx, queen[sx])) return false;
        }
        return dfs(queen, x + 1);
    }

    for (int y = 0; y < 8; ++y) {
        bool judge = true;
        for (int sx = 0; sx < x; ++sx) {
            if (sameline(x, y, sx, queen[sx])) judge = false;
        }

        if (judge) {
            queen[x] = y;
            if (dfs(queen, x + 1)) return true;
            queen[x] = -1;
        }
    }
    return false;
}

int main() {
    int N;
    std::cin >> N;
    std::vector<int> queen(8, -1);
    for (int i = 0; i < N; ++i) {
        int x, y;
        std::cin >> x >> y;
        queen[x] = y;
    }

    if (!dfs(queen, 0)) std::terminate();

    std::vector<std::string> ans(8, std::string(8, '.'));
    for (int x = 0; x < 8; ++x) ans[x][queen[x]] = 'Q';

    for (auto& s : ans) std::cout << s << std::endl;
    return 0;
}

