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...
def main():
    import itertools

    k = int(input())
    cr_lis = []
    for _ in range(k):
        cr_lis.append(list(map(int, input().split())))

    eight_lis = [x for x in range(8)]
    per_lis = itertools.permutations(eight_lis)



    for test in per_lis:
        #print(test)
        cnt = 0
        tmp = 0
        for queen_in in cr_lis:
            if test[queen_in[0]] != queen_in[1]:
                cnt += 1
        if cnt > 0:
            continue
        zero_lis_1 = [0 for _ in range(8)]
        zero_lis_2 = [0 for _ in range(8)]
        zero_lis_3 = [0 for _ in range(8)]
        zero_lis_4 = [0 for _ in range(8)]
        zero_lis_5 = [0 for _ in range(8)]
        zero_lis_6 = [0 for _ in range(8)]
        zero_lis_7 = [0 for _ in range(8)]
        zero_lis_8 = [0 for _ in range(8)]

        check_lis = []
        dot_lis_1 = ["." for _ in range(8)]
        dot_lis_2 = ["." for _ in range(8)]
        dot_lis_3 = ["." for _ in range(8)]
        dot_lis_4 = ["." for _ in range(8)]
        dot_lis_5 = ["." for _ in range(8)]
        dot_lis_6 = ["." for _ in range(8)]
        dot_lis_7 = ["." for _ in range(8)]
        dot_lis_8 = ["." for _ in range(8)]


        check_lis.append(zero_lis_1)
        check_lis.append(zero_lis_2)
        check_lis.append(zero_lis_3)
        check_lis.append(zero_lis_4)
        check_lis.append(zero_lis_5)
        check_lis.append(zero_lis_6)
        check_lis.append(zero_lis_7)
        check_lis.append(zero_lis_8)

        ans_lis = []
        ans_lis.append(dot_lis_1)
        ans_lis.append(dot_lis_2)
        ans_lis.append(dot_lis_3)
        ans_lis.append(dot_lis_4)
        ans_lis.append(dot_lis_5)
        ans_lis.append(dot_lis_6)
        ans_lis.append(dot_lis_7)
        ans_lis.append(dot_lis_8)


        retsu = -1
        #print(check_lis)
        for c in test:
            retsu += 1
            check_lis[c][retsu] = 1
        #print(check_lis)

        retsu = -1
        for c in test:
            retsu += 1
            cnt_retsu = retsu
            cnt_c = c

            while 7>= cnt_retsu > 0 and 7>= cnt_c > 0: #左上へ
                if check_lis[cnt_c - 1][cnt_retsu - 1] == 1:
                    tmp += 1
                cnt_c -= 1
                cnt_retsu -= 1
            cnt_retsu = retsu
            cnt_c = c
            while 0<= cnt_retsu < 7 and 7>= cnt_c > 0: #右上へ
                if check_lis[cnt_c - 1][cnt_retsu + 1] == 1:
                    tmp +=1
                cnt_c -= 1
                cnt_retsu += 1
            cnt_retsu = retsu
            cnt_c = c
            while 7 >= cnt_retsu > 0 and 0<= cnt_c < 7: #左下へ
                #print(cnt_c, cnt_retsu)
                if check_lis[cnt_c + 1][cnt_retsu - 1] == 1:
                    tmp += 1
                cnt_c += 1
                cnt_retsu -= 1
            cnt_retsu = retsu
            cnt_c = c
            while 0<= cnt_retsu < 7 and 0<= cnt_c < 7: #右下へ
                if check_lis[cnt_c + 1][cnt_retsu + 1] == 1:
                    tmp += 1
                cnt_c += 1
                cnt_retsu += 1
        #print(check_lis)
        if tmp > 1:
            pass
        else:
            for i in range(8):
                ans_lis[i][test[i]] = "Q"
                for ans in ans_lis[i]:
                    if ans == "Q":
                        pass
                    else:
                        ans = "."
            for ans in ans_lis:
                print(''.join(map(str, ans)))
            exit()




if __name__ == "__main__":
    main()

