룩 배치 완성하기

바이티(Bytie)는 오랜 노력 끝에 $n \times n$ 크기의 체스판 위에 룩(rook) $n$개를 서로 공격하지 않도록 놓는 데 성공했습니다. 참고로 룩은 자신과 같은 행 또는 같은 열에 있는 모든 칸을 공격합니다.

그런데 실수로 체스판을 건드리는 바람에 룩 몇 개가 판에서 떨어져 버렸습니다. 판 위에 남아 있는 룩은 원래 자리에 그대로 두고, 떨어진 룩들을 다시 올려서 룩 $n$개가 서로 공격하지 않는 배치를 다시 완성해 주세요.

첫째 줄에 체스판의 크기를 나타내는 정수 $n$ ($2 \le n \le 1\,000$)이 주어집니다. 이어지는 $n$개의 줄에는 현재 배치가 주어지며, 각 줄은 $n$개의 문자로 이루어집니다. 문자 '.'은 빈 칸을, 문자 'W'는 룩이 놓인 칸을 나타냅니다.

판 위에는 룩이 $w$개 있으며 $1 \le w \le n - 1$을 만족합니다. 또한 판 위의 어떤 두 룩도 서로 공격하지 않습니다.

완성된 배치를 나타내기 위해 각 줄에 '.' 또는 'W' 문자 $n$개를 담은 줄을 $n$개 출력하세요. 출력한 배치에는 룩이 정확히 $n$개 있어야 하고, 처음부터 판 위에 있던 룩들은 원래 위치에 그대로 있어야 하며, 어떤 두 룩도 서로 공격하지 않아야 합니다.

떨어진 룩 $n - w$개를 놓는 방법이 여러 가지일 수 있으므로, 그중 사전순으로 가장 작은 배치를 출력하세요. 여기서 배치는 출력되는 줄을 위에서 아래로, 각 줄 안에서는 왼쪽에서 오른쪽으로 이어 붙인 문자열로 보고 비교하며, 문자 '.'이 문자 'W'보다 앞선다고 간주합니다.