Generate all safe queen placements on board

You are given an integer n representing the size of a chessboard (n × n). You need to place n queens on the board so that no two queens attack each other.

A queen can attack another piece if they are on the same row, same column, or same diagonal.

Return all distinct valid configurations of the board.

• Each configuration should be represented as an array (or list) of n strings.
• Each string has length n and represents one row of the board.
• Character 'Q' represents a queen, and '.' represents an empty square.

Two configurations are considered different if they differ in at least one row string.

You may assume:

• 1 ≤ n ≤ 9.

Example

Input:

n = 4

One valid output (order of configurations and rows does not matter):

[
 [".Q..",
 "...Q",
 "Q...",
 "..Q."],

 ["..Q.",
 "Q...",
 "...Q",
 ".Q.."]
]

In each configuration above, there are 4 queens on the board, and no two queens attack each other.