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...
class eight_Q:
    #Free = 'Free', NOT_Free = 'NotFree'
    N = 8

    def __init__(self):
        #self.position = [['Free' for i in range(self.N)] for j in range(self.N)]
        self.row = [-1 for _ in range(self.N)]
        self.col = ['Free' for _ in range(self.N)]
        self.dpos = ['Free' for _ in range(self.N*2 -1)]
        self.dneg = ['Free' for _ in range(self.N*2 -1)]
        self.initial = [-1 for _ in range(self.N)]

    def initQueen(self,i,j):
        self.row[i] = j
        self.initial[i] = j
        self.col[j] = 'NotFree'
        self.dpos[i+j] = 'NotFree'
        self.dneg[i-j+(self.N-1)] = 'NotFree'

    def putQueen(self, i):
        for j in range(self.N):
            #print(j)
            if i == self.N:
                return 'Success'
            if self.initial[i] == j:
                if self.putQueen(i+1) == 'Success':
                    return 'Success'
                else:
                    continue
            if self.col[j] == 'Free' and self.dpos[i+j] == 'Free' and self.dneg[i-j+(self.N-1)] == 'Free':
                #put queen at (i, j)
                self.row[i] = j
                self.col[j] = 'NotFree'
                self.dpos[i+j] = 'NotFree'
                self.dneg[i-j+(self.N-1)] = 'NotFree'
                #try the next row
                if i == self.N-1:
                    return 'Success'
                else:
                    if self.putQueen(i+1) == 'Success':
                        return 'Success'
                    #remove the queen at (i, j) for backtracking
                    else:
                        self.row[i] = -1
                        self.col[j] = 'Free'
                        self.dpos[i+j] = 'Free'
                        self.dneg[i-j+(self.N-1)] = 'Free'

        return 'Fail'

    def printBoard(self):
        #print(self.row)
        for i in range(self.N):
            for j in range(self.N):
                if self.row[i] == j:
                    print("Q",end='')
                elif self.initial[i] == j:
                    print("Q",end='')
                else:
                    print(".",end='')
            print()


if __name__ == "__main__":
    eightQueen = eight_Q()
    k = int(input())

    for i in range(k):
        _i, _j = (int(z) for z in input().split())
        eightQueen.initQueen(_i, _j)
    if eightQueen.putQueen(0) == 'Success':
        eightQueen.printBoard()
        #print(eightQueen.row)
    else:
        print("Fail to put queen")
        #print(eightQueen.row)

