Queens (3) P38211

Write a program to print the lexicographically smallest way to place $n$ queens on an $n \times n$ chessboard so that no queen threatens another queen.

Input

Input consists of a natural number $n > 0$.

Output

Mark the queens with a ‘Q’, and the empty positions with a dot. Print the lexicographically smallest way (by rows, from top to bottom, and assuming that a ‘Q’ is smaller than a dot) to place $n$ queens on an $n \times n$ chessboard so that no queen threatens another queen. If there is no solution, print “NO SOLUTION”.