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 {
	Scanner sc = new Scanner(System.in);
	
	final int N = 8;
	//matrix
	int[] row = new int[N];
	boolean[] col = new boolean[N];
	boolean[] dpos = new boolean[2*N-1];
	boolean[] dneg = new boolean[2*N-1];
	
	//input
	int k, r, c;
	
	public void input() {
		Arrays.fill(row, -1);
		k = sc.nextInt();
		for(int i=0; i<k; i++) {
			r = sc.nextInt();
			c = sc.nextInt();
			row[r] = c;
			col[c] = dpos[r+c] = dneg[r-c+N-1] = true;
		}
		recursive(0);
	}
	
	public void recursive(int i) {
		if(i == N) {
			output();
			return;
		}
		if(row[i] != -1) {
			recursive(i+1);
		}
		for(int j=0; j<N; j++) {
			if(row[i] !=-1 || col[j] || dpos[i+j] || dneg[i-j+N-1]) {
				continue;
			}
			row[i] = j;
			col[j] = dpos[i+j] = dneg[i-j+N-1] = true;
			recursive(i+1);
			row[i] = -1;
			col[j] = dpos[i+j] = dneg[i-j+N-1] = false;
		}
	}
	
	public void output() {
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(row[i] == j) {
					System.out.print("Q");
				}else {
					System.out.print(".");
				}
			}
			System.out.println();
		}
	}
	
	public static void main(String[] args) {
		Main obj = new Main();
		obj.input();
	}
}

