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.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    private static List<Queen> queenList;

    private static String ansQueenPermutation = "";

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int k = Integer.parseInt(scan.next());
        queenList = new ArrayList<Queen>(8);
        for (int i = 0; i < k; i++) {
            int r = Integer.parseInt(scan.next());
            int c = Integer.parseInt(scan.next());
            queenList.add(new Queen(r, c));
        }
        scan.close();

        permutation("01234567", "");

        for (int i = 0; i < 8; i++) {
            int queen = Integer.parseInt(ansQueenPermutation.substring(i, i + 1));
            for (int j = 0; j < 8; j++) {
                if (j == queen) {
                    System.out.print("Q");
                } else {
                    System.out.print(".");
                }
            }
            System.out.println("");
        }
    }

    private static void permutation(String s, String ans) {
        if (s.length() == 1) {
            String permu = ans + s;
            int[] permuR = new int[8];
            int[] permuC = new int[8];
            for (int i = 0; i < 8; i++) {
                permuR[i] = i;
                permuC[i] = Integer.parseInt(permu.substring(i, i + 1));
            }

            // 入力の制約チェック
            for (Queen queen : queenList) {
                if (queen.c != permuC[queen.r]) {
                    return;
                }
            }

            // 斜め方向の制約チェック
            for (int i = 0; i < 8; i++) {
                for (int j = i + 1; j < 8; j++) {
                    if (permuR[i] - permuR[j] == permuC[i] - permuC[j]) {
                        return;
                    }
                    if (permuR[i] + permuC[i] == permuR[j] + permuC[j]) {
                        return;
                    }
                }
            }

            ansQueenPermutation = permu;
            return;
        }

        for (int i = 0; i < s.length(); i++) {
            permutation(s.substring(0, i) + s.substring(i + 1), ans + s.charAt(i));
        }
    }

    static class Queen {
        int r;
        int c;

        public Queen(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }

}

