섬

자가용 비행기로 태평양 한가운데를 비행하던 튜브는 연료가 부족해 외딴섬 한가운데에 불시착했다. 다행히 튜브는 섬 근방 지역의 정보가 모두 담긴 $N \times M$ 격자 지도를 발견했다.

지도의 각 칸은 바다 또는 육지다. 최외곽 칸은 모두 바다이다. 칸의 좌표는 $(x, y)$ ($1 \le x \le N$, $1 \le y \le M$)로 나타내며, $x = 1$, $x = N$, $y = 1$, $y = M$ 중 하나라도 만족하는 칸은 바다임이 보장된다. 모든 육지 칸은 어떤 섬의 일부이다. 변을 맞대고 인접한 두 육지 칸은 같은 섬으로 본다. 즉, $(x, y)$와 $(x+1, y)$가 모두 육지이면 두 칸은 같은 섬에 속하고, $(x, y)$와 $(x, y+1)$이 모두 육지이면 이 둘도 같은 섬에 속한다.

튜브는 현재 위치에서 뗏목을 주웠고, 이 뗏목으로 망망대해를 건너 연료를 찾으러 떠날 계획이다. 튜브는 임의의 칸에서 상하좌우로 인접한 칸으로 이동할 수 있다. 이동할 때 도착하는 칸이 육지인지 바다인지는 상관없다(뗏목을 주웠으니까!). 튜브의 목표는 현재 위치에서 이렇게 이동해 먼 바다에서 연료를 구한 뒤 돌아오는 것이다.

튜브에게는 두 가지 문제가 있다. 첫째, 불시착한 지역의 섬 중 하나에는 오리를 잡아먹으려는 무서운 사냥꾼들이 살고 있다. 튜브가 있는 섬은 안전함이 확인되었지만, 탈출할 때 사냥꾼이 있는 섬을 지나야 한다면 튜브는 큰 위험에 처한다. 둘째, 튜브는 지도의 어느 섬에 있는지 알지 못한다. 튜브가 있는 섬은 최외곽 바다와 바로 맞닿아 있을 수도 있고, 다른 섬들에 겹겹이 둘러싸인 위험한 곳일 수도 있다.

튜브는 지도에 있는 모든 섬이 안전한지 위험한지 알고 싶어 한다. 섬 $S$가 위험하다는 것은, $S$에서 최외곽 칸으로 가려면 반드시 지나야 하는 다른 섬 $T$가 존재한다는 뜻이다. 섬 $S$가 안전하다는 것은 $S$가 위험하지 않다는 뜻이다. 지도의 섬 중 안전한 섬과 위험한 섬을 구분해 알려주자.

첫 번째 줄에 격자의 크기 $N$과 $M$이 공백으로 구분되어 주어진다. ($3 \le N, M \le 2{,}000$)

이후 $N$개의 줄에 길이 $M$의 문자열이 주어진다. $i$번째 줄의 $j$번째 문자는 $(i, j)$ 칸의 상태를 나타내며, #이면 육지, .이면 바다이다. 이 외의 문자는 주어지지 않는다. 격자 안에는 육지 칸이 하나 이상 있다.

$N$개의 줄에 길이 $M$의 문자열을 출력한다. $i$번째 줄의 $j$번째 문자는 $(i, j)$ 칸의 상태를 나타낸다. 바다 칸에는 ., 안전한 섬의 일부인 칸에는 O, 위험한 섬의 일부인 칸에는 X를 출력한다.