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...
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.*;
import java.awt.Point;

public class Main {
    // static int INF = (1 << 30) - 1;
    // static long L_INF = (1L << 62) - 1;
    // static long MOD = (long) 1e9 + 7;

    static class Solver {
        int k;
        HashMap<Integer, Point> mp;

        boolean check(ArrayList<Point> al, Point p1) {
            for (Point p2 : al) {
                if (p1.x == p2.x) {
                    return false;
                }
                if (Math.abs(p1.x - p2.x) == Math.abs(p1.y - p2.y)) {
                    return false;
                }
            }
            return true;
        }

        ArrayList<Point> rec(ArrayList<Point> al, int idx) {
            if (idx == 8) {
                return al;
            }
            ArrayList<Point> newPoints = new ArrayList<>();
            if (mp.containsKey(idx)) {
                newPoints.add(mp.get(idx));
            } else {
                for (int i = 0; i < 8; i++) {
                    newPoints.add(new Point(i, idx));
                }
            }
            for (Point p : newPoints) {
                if (check(al, p)) {
                    @SuppressWarnings("unchecked")
                    ArrayList<Point> newAL = (ArrayList<Point>) al.clone();
                    newAL.add(p);
                    ArrayList<Point> ans = rec(newAL, idx + 1);
                    if (ans != null) {
                        return ans;
                    }
                }
            }
            return null;
        }

        // write your code
        void solve(InputReader in, PrintWriter out) {
            k = in.nextInt();
            mp = new HashMap<>();
            for (int i = 0; i < k; i++) {
                int r = in.nextInt();
                int c = in.nextInt();
                mp.put(c, new Point(r, c));
            }

            ArrayList<Point> al = rec(new ArrayList<Point>(), 0);
            char[][] ans = new char[8][8];
            for (int i = 0; i < 8; i++) {
                Arrays.fill(ans[i], '.');
            }
            for (Point p : al) {
                ans[p.x][p.y] = 'Q';
            }
            for (int i = 0; i < 8; i++) {
                for (int j = 0; j < 8; j++) {
                    out.print(ans[i][j]);
                }
                out.println();
            }
        }

        void debug(Object... os) {
            System.err.println(Arrays.deepToString(os));
        }
    }

    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Solver solver = new Solver();
        solver.solve(in, out);
        out.close();
    }

    static class InputReader {
        BufferedReader reader;
        StringTokenizer tokenizer;

        InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }
    }
}

