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 <iostream>
#include <cstring>
using namespace std;
int a[8][8], f[8], b[8], c[15], d[15];

void search(int n)
{
	if (n >= 8)
	{
		for (int k = 0; k < 8; ++k)
		{
			for (int j = 0; j < 8; ++j)
			{
				if (a[k][j])
					cout << "Q";
				else
					cout << ".";
			}
			cout << endl;
		}
	}
	else
	{
		if (f[n])
			search(n + 1);
		else
		for (int i = 0; i < 8; ++i)
		{
			if (!b[i] && !c[i + n] && !d[n - i + 7])
			{
				b[i] = 1;
				c[i + n] = 1;
				d[n - i + 7] = 1;
				a[n][i] = 1;
				search(n + 1);
				b[i] = 0;
				c[i + n] = 0;
				a[n][i] = 0;
				d[n - i + 7] = 0;
			}
		}
	}
}

int main()
{
	int n;
	cin >> n;
	while (n--)
	{
		int v, c1;
		cin >> v >> c1;
		a[v][c1] = 1;
		b[c1] = 1;
		f[v] = 1;
		c[v + c1] = 1;
		d[v - c1 + 7] = 1;
	}
	search(0);
	return 0;
}
