물류 센터

Sokoban은 이 도시에서 가장 큰 물류 센터의 최고 직원이다. 그는 단순하지만 체력을 많이 쓰는 이 일을 좋아한다. 매일 상자를 가능한 목적지까지 밀어 두면, 그곳에서 상자를 트럭에 싣는다. 그러나 젊은 시절은 지났고, 육체노동의 부담이 느껴지기 시작했다. 그래서 상자를 최적으로 옮기도록 돕는 알고리즘, 즉 Fast Pushing Crates(FPC) 알고리즘을 만들었다. 이 알고리즘을 완성하려면 당신의 도움이 필요하다.

그의 알고리즘은 물류 센터의 배치를 격자로 입력받아, 상자를 효율적으로 미는 데 필요한 이동 순서를 반환한다. 알고리즘에서는 격자 안의 데드 스퀘어를 찾아야 한다. 어떤 칸이 벽이거나, Sokoban이 어느 위치로든 순간이동할 수 있다고 가정해도 그 칸에서 상자를 어떤 목적지로도 옮길 수 없다면, 그 칸을 데드 스퀘어라고 한다.

물류 센터의 배치가 주어졌을 때 데드 스퀘어를 찾아라.

첫 줄에 두 정수 $r$과 $c$($1\leq r,c\leq 10^3$)가 주어진다. 격자의 행 수와 열 수이다.

이어지는 $r$개의 줄에는 각각 $c$개의 문자가 주어진다.

• \#은 벽이다. 격자는 벽으로 둘러싸여 있다고 보장된다.
• D는 목적지이다. 0개를 포함해 몇 개든 있을 수 있다.
• .은 빈 칸이다.

$r$개의 줄을 출력한다. 각 줄은 $c$개의 문자로 이루어진다. $j$번째 줄의 $i$번째 문자는 다음과 같다.

• 위치 $(i,j)$의 칸이 데드 스퀘어이면 X.
• 그렇지 않으면 O.