시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB14101071.429%

문제

에린 대륙에는 고대 마법이 깃든 $N \times N$ 크기의 룬 격자가 존재한다. 단, 일부 칸에는 봉인된 룬이 있어 지나갈 수 없으며, $1$행, $1$열, $N$행과 $N$열에는 봉인된 룬이 없음이 보장된다.

마비노기의 고급 마법사인 밀레시안은 룬의 상태를 점검하기 위해 격자의 왼쪽 위인 $(1,1)$에서 오른쪽 아래인 $(N,N)$까지 이동한 뒤 다시 $(1,1)$로 돌아오는 왕복 경로를 설정하려 한다. 구체적으로, 밀레시안은 다음과 같은 두 경로를 따라 이동한다.

  1. 정방향 경로: $(1,\,1)$에서 $(N,\,N)$으로 이동하며, 행과 열이 증가하는 방향으로만 이동하는 경로이다.
  2. 역방향 경로: $(N,\,N)$에서 $(1,\,1)$으로 이동하며, 행과 열이 감소하는 방향으로만 이동하는 경로이다.

$(1,\,1)$, $(N,\,N)$을 제외한 모든 칸에서 정방향 경로와 역방향 경로는 같은 칸을 공유할 수 없으며, 격자를 위에서 아래로 보았을 때 정방향 경로는 항상 역방향 경로의 위쪽을 따라 이동한다. 따라서, 전체 왕복 경로는 시계 방향으로 이루어진다.

봉인되지 않은 모든 룬 칸은 흰색 또는 검은색의 두 상태 중 하나이다. 처음에는 모든 룬 칸이 흰색이다.

밀레시안이 어떤 칸을 한 번 지날 때마다, 해당 칸의 룬 상태는 반전된다(흰색 $\leftrightarrow$ 검은색). 단, 왕복 과정에서 $(1,1)$과 $(N,N)$은 각각 두 번 지나가는 것으로 생각하며, 이 두 칸의 룬은 항상 흰색 상태로 유지된다.

밀레시안은 가능한 서로 다른 모든 왕복 경로를 정확히 한 번씩 주행해 보았다. (정방향 경로 또는 역방향 경로에서 지나간 칸이 하나라도 다르면 서로 다른 경로로 간주한다.)

모든 왕복 경로를 주행한 뒤, 각 룬 칸의 최종 상태를 구하여라.

입력

첫 번째 줄에 $N$이 주어진다. ($3 \leq N \leq 2 \, 000$)

두 번째 줄부터 $N$개의 줄에 걸쳐 격자의 정보가 문자열로 주어진다. .이면 봉인되지 않은 룬이 있는 칸, #이면 봉인된 룬이 있어 지나가지 못하는 칸이다.

출력

모든 왕복 경로를 한 번씩 주행한 뒤의 격자 상태를 출력한다. 입력과 같은 형식으로 $N$개의 줄에 걸쳐 출력하며, 흰색 룬은 W, 검은색 룬은 B, 봉인된 룬은 #으로 출력한다.

$(1,1)$과 $(N,N)$은 항상 "W"를 출력함에 유의하라.

예제 입력 1

3
...
...
...

예제 출력 1

WBW
BWB
WBW

가능한 모든 왕복 경로는 다음과 같다.

예제 입력 2

4
....
....
.##.
....

예제 출력 2

WBWB
BBWB
B##B
BBBW

가능한 모든 왕복 경로는 다음과 같다.