Queen Placement Problem

Given an \(N \times N\) chessboard, you must sequentially place queens on empty cells such that the total number of queens is maximized. A queen can be placed in a cell if and only if that cell is attacked by an even number of queens placed so far. A queen attacks another cell if and only if they share the same row, the same column, or the same diagonal (both main and anti-diagonals). Your task is to output one valid configuration of queen placements on the board.

Note: The initial board is empty. A cell with 0 attacking queens (and hence 0, an even number) is eligible for placing a queen. The placements are made in a fixed order (row-major order) to maximize the number of queens under the above constraint.

All formulas are in \(\LaTeX\) format.

inputFormat

The input consists of a single integer \(N\) (\(1 \le N \le 100\) for instance) which denotes the size of the chessboard.

outputFormat

Output the final board configuration in \(N\) lines. Each line should contain \(N\) characters where a 'Q' represents a queen and a '.' represents an empty cell. The configuration must satisfy that a queen is placed (in the sequence of checking cells in row-major order) only when the cell is attacked by an even number of queens already placed.

sample

1

Q