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{

	public static void main(String[] args){

		Scanner scan = new Scanner(System.in);
		int k = scan.nextInt();
		HS hs = new HS();

		for(int i = 0; i < k; i++){
			int r = scan.nextInt();
			int c = scan.nextInt();
			hs.add(i, r, c);
		}
		hs.solve();

		for(int r = 0; r < 8; r++){
			for(int c = 0; c < 8; c++)
				if(hs.isQuenn(r, c))
					System.out.print("Q");
				else
					System.out.print(".");
			System.out.println();
		}

		scan.close();
		System.exit(0);
	}
}

class HS{
	int[] row;
	int[] col;

	public HS(){
		row = new int[8];
		col = new int[8];
		for(int i = 0; i < 8; i++){
			row[i] = -1;
			col[i] = -1;
		}
	}

	public void add(int i, int r, int c){
		row[i] = r;
		col[i] = c;
	}

	public void solve(){
		int k = 0; // ??????????¨????
		for(; k < row.length; k++) // ??????????¨??????????????????????
			if(row[k] == -1) // k?????????????±??????????
				break;
		sol(k); // k??????????????????????????????????????????????§£???
	}
	private boolean sol(int k){
		if(k == 8) // ???????????????0??????7????????§????????????
			return true; // ????????????
		for(int r = 0; r < 8; r++)
			for(int c = 0; c < 8; c++)
				if(isAbl(r, c)){
					row[k] = r;
					col[k] = c;
					if(sol(k+1)) // ?¬??????????????????????????????????
						return true; // ????????????
					else{ // ??????????????£??????k???????????????????¶????
						row[k] = -1;
						col[k] = -1;
					}
				}
		return false;
	}
	private boolean isAbl(int r, int c){
		for(int k = 0; k < 8; k++){
			if(row[k] == -1) // row[k]???????¨??????????break??????return true??????
				break;
			if(row[k] == r || col[k] == c || row[k] + col[k] == r + c || row[k] - col[k] == r - c){
				// ??????????????????false?¨???????????????????????????????false????????????????????¨????????????????????????false??????????????????????????¨????????????????????????false??????????????????
				return false;
			}
		}
		return true;
	}

	public boolean isQuenn(int r, int c){
		for(int k = 0; k < 8; k++)
			if(row[k] == r && col[k] == c) // k??¨?????¨??????????????????
				return true; // ????????????
		return false; // ????????????
	}
}