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.Scanner;
public class Main {
private static Scanner s = new Scanner(System.in);
private static int n = s.nextInt();
static int a,b;
static int[] m = new int[8];
static boolean[] col = new boolean[8];
static boolean[] dpos = new boolean[2*8-1];
static boolean[] dneg = new boolean[2*8-1];
public static void main(String[] args) {
	for(int i = 0;i < 8;i++) {
		m[i] = -1;
	}
	for(int i = 0;i < n;i++) {
		a = s.nextInt();
		b = s.nextInt();
		m[a] = b;
		col[b] = dpos[a+b]  = dneg[a - b + 7] = true;
	}
	putQ(0);
}


static void putQ(int i) {
	if(i == 8) {
		print();
		return;
	}

	if(m[i] != -1) putQ(i+1);
	for(int j = 0;j < 8;j++) {
		if(m[i] != -1 || col[j] || dpos[i+j] || dneg[i - j + 7]) continue;

		m[i] = j;
		col[j] = dpos[i+j] = dneg[i - j + 7] = true;
		putQ(i+1);
		m[i] = -1;
		col[j] = dpos[i+j] = dneg[i - j + 7] = false;
	}
}
static void print(){
	for(int i = 0; i < 8;i++) {
		for(int j = 0;j < 8;j++) {
			if(m[i] == j) {
				System.out.print("Q");
			}else {
				System.out.print(".");
			}
		}
		System.out.println();
	}
}
}
