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 <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
	int N; cin >> N;

	int x, y;

	vector<int> y_x(8, -1);

	for (int i = 0; i < N; i++)
	{
		cin >> y >> x;

		y_x[y] = x;
	}

	vector<int> perm(8);

	for (int i = 0; i < 8; i++) { perm[i] = i; }

	bool ok = true;

	do
	{
		ok = true;

		for (int y = 0; y < 8; y++)
		{
			if (y_x[y] != -1 && perm[y] != y_x[y])
			{
				ok = false;
			}
		}

		if (ok == true)
		{
			for (int i = 0; i < 8; i++)
			{
				for (int j = 0; j < 8; j++)
				{
					if (i != j)
					{
						if (i - perm[i] == j - perm[j] || i + perm[i] == j + perm[j])
						{
							ok = false;
						}
					}
				}
			}
		}

		if (ok == true)
		{
			for (int i = 0; i < 8; i++)
			{
				for (int j = 0; j < 8; j++)
				{
					if (perm[i] == j)
					{
						cout << 'Q';
					}
					else
					{
						cout << '.';
					}
				}

				cout << endl;
			}
		}
	} while (next_permutation(perm.begin(), perm.end()));

	return 0;
}