Rooks

Interview

Time limit1sMemory limit128 MB

Summary

Complete a partially filled n by n board to a full non-attacking rook placement, choosing the lexicographically smallest completion.

Level: Medium6 of 10
Topics: Greedy, Sorting, Implementation, Array
Solved: No attempts yet

Problem

After a lot of effort, Bytie has finally managed to place $n$ rooks on an $n \times n$ board so that no two of them attack each other. As a reminder, a rook attacks every square that lies in the same row or the same column as it.

Unfortunately, Bytie has now accidentally bumped the board and several rooks have fallen off. Leaving every rook that is still on the board exactly where it is, help Bytie put the fallen rooks back so that all $n$ rooks are on the board again and no two of them attack each other.

Input

The first line contains one integer $n$ ( $2 \le n \le 1\,000$ ), the size of the board. Each of the next $n$ lines contains $n$ characters describing the current configuration. The character '.' is an empty square, and the character 'W' is a square occupied by a rook.

There are $w$ rooks on the board with $1 \le w \le n - 1$ , and no two of them attack each other.

Output

Print $n$ lines of $n$ characters each ('.' or 'W') describing the completed board. It must contain exactly $n$ rooks, keep every initial rook in its original position, and have no two rooks attacking each other.

Because the $n - w$ fallen rooks can be placed in more than one way, print the lexicographically smallest such board. Treat the board as the string formed by its output lines read top to bottom, each line left to right, and consider '.' to come before 'W'.

Examples4

Example 1

Input

8
........
.....W..
..W.....
.......W
W.......
........
.W......
........

Expected output

......W.
.....W..
..W.....
.......W
W.......
....W...
.W......
...W....

Example 2
Input
```
2
W.
..
```
Expected output
```
W.
.W
```
Example 3
Input
```
2
..
.W
```
Expected output
```
W.
.W
```
Example 4
Input
```
3
...
.W.
...
```
Expected output
```
..W
.W.
W..
```