時間制限 : sec, メモリ制限 : KB
English / Japanese  

8クイーン問題

8 クイーン問題とは、$8 \times 8$ のマスから成るチェス盤に、どのクイーンも他のクイーンを襲撃できないように、8 つのクイーンを配置する問題です。チェスでは、クイーンは次のように8方向のマスにいるコマを襲撃することができます。


すでにクイーンが配置されている $k$ 個のマスが指定されるので、それらを合わせて8つのクイーンを配置したチェス盤を出力するプログラムを作成してください。

入力

1行目に整数 $k$ が与えられます。続く $k$ 行にクイーンが配置されているマスが2つの整数 $r$, $c$ で与えられます。$r$, $c$ はそれぞれ0から始まるチェス盤の行と列の番号を表します。

出力

出力は $8 \times 8$ のチェス盤を表す文字列で、クイーンが配置されたマスを 'Q'、配置されていないマスを '.' で表します。

制約

  • 入力に対する解はただ1つ存在する。

入力例 1

2
2 2
5 3

出力例 1

......Q.
Q.......
..Q.....
.......Q
.....Q..
...Q....
.Q......
....Q...