Quân hậu

Cho bàn cờ \(N \times N\). Một số quân hậu đã được đặt sẵn. Hãy đặt thêm các quân hậu còn lại để mỗi hàng và mỗi cột có đúng một quân hậu, đồng thời không có hai quân hậu nào tấn công nhau. Nếu không thể, in ra "NO".

\InputFile
Dòng đầu chứa số nguyên \(N\) (\(1 \le N \le 20\))

Tiếp theo là \(N\) dòng, mỗi dòng là một xâu dài \(N\) ký tự, mỗi ký tự là . (ô trống) hoặc Q (một quân hậu đã đặt sẵn).

\OutputFile
Nếu không có lời giải, in ra NO.

Ngược lại, in ra YES ở dòng đầu, sau đó in \(N\) dòng mô tả một cấu hình hợp lệ ở cùng định dạng đầu vào (dùng . và Q).

Example

4
..Q.
....
....
....

YES
..Q.
Q...
...Q
.Q..