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...
#include <cstdio>
using namespace std;
char G[8][8];
bool row[8], col[8], dpos[15], dneg[15];
void dfs(int cur) {
	if (cur == 8) {
		for (int i = 0; i < 8; i++) {
	    	for (int j = 0; j < 8; j++) {
	    		putchar(G[i][j]);
			}
			putchar('\n');
		}
	}
	else {
		if (row[cur]) dfs(cur + 1);
		else {
			for (int i = 0; i < 8; i++) {
				if (!col[i] && !dpos[i + cur] && !dneg[cur - i + 7]) {
					row[cur] = true;
					col[i] = true;
					dpos[i + cur] = true;
					dneg[cur - i + 7] = true;
					G[cur][i] = 'Q';
					dfs(cur + 1);
					row[cur] = false;
					col[i] = false;
					dpos[i + cur] = false;
					dneg[cur - i + 7] = false;
					G[cur][i] = '.';
				}
			}
		}
	}
}
int main() {
    for (int i = 0; i < 8; i++) {
    	for (int j = 0; j < 8; j++) {
    		G[i][j] = '.';
		}
	}
	int k;
	scanf("%d", &k);
	while (k--) {
		int x, y;
		scanf("%d%d", &x, &y);
		G[x][y] = 'Q';
		row[x] = true;
		col[y] = true;
		dpos[x + y] = true;
		dneg[x - y + 7] = true;
	}
	dfs(0);
	return 0;
}
