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.*;

public class Main {

    static char[][] map;

    static boolean next_permutation(int[] p) {
      for (int a = p.length - 2; a >= 0; --a)
        if (p[a] < p[a + 1])
          for (int b = p.length - 1;; --b)
            if (p[b] > p[a]) {
              int t = p[a];
              p[a] = p[b];
              p[b] = t;
              for (++a, b = p.length - 1; a < b; ++a, --b) {
                t = p[a];
                p[a] = p[b];
                p[b] = t;
              }
              return true;
            }
      return false;
    }

    static boolean search(int i, int j) {
        boolean flg = true;
        for (int r=0;r<8;r++){
            if (r==i) continue;
            if (map[r][j]=='Q') {
                flg = false;
            }
        }
        for (int c=0;c<8;c++) {
            if (c==j) continue;
            if (map[i][c]=='Q') {
                flg = false;
            }
        }
        for (int k=-Math.min(i, j);k<=Math.min(7-i, 7-j);k++) {
            if (k==0) continue;
            if (map[i+k][j+k]=='Q') {
                flg = false;
            }
        }
        for (int k=-Math.min(i, 7-j);k<=Math.min(7-i, j);k++) {
            if (k==0) continue;
            if (map[i+k][j-k]=='Q') {
                flg = false;
            }
        }
        return flg;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int[] r = new int[k];
        int[] c = new int[k];
        for (int i=0;i<k;i++) {
            r[i] = sc.nextInt();
            c[i] = sc.nextInt();
        }

        int[] arr = new int[8];
        for (int i=0;i<8;i++) {
            arr[i] = i;
        }
        do {
            boolean flag = true;
            map = new char[8][8];
            for (int i=0;i<8;i++) {
                for (int j=0;j<8;j++) {
                    map[i][j] = '.';
                }
            }
            for (int i=0;i<k;i++) {
                map[r[i]][c[i]] = 'Q';
            }
            for (int i=0;i<8;i++) {
                map[i][arr[i]] = 'Q';
            }

            loop:for (int i=0;i<8;i++) {
                for (int j=0;j<8;j++) {
                    if (map[i][j]=='Q') {
                        if (!search(i, j)) {
                            flag = false;
                            break loop;
                        }
                    }
                }
            }

            if (flag) {
                for (int i=0;i<8;i++) {
                    for (int j=0;j<8;j++) {
                        if (j!=7) System.out.print(map[i][j]);
                        else System.out.println(map[i][j]);
                    }
                }
                break;
            }
        } while (next_permutation(arr));
    }
}
