RoboThieves

로봇이 공장에서 보물을 훔쳤고, 들키지 않고 탈출해야 한다. 공장은 N행 M열 격자로 나타낼 수 있으며, 로봇은 상하좌우로 움직인다.

격자의 각 칸은 빈 칸, 벽, 카메라, 컨베이어, 로봇의 시작 위치 중 하나이다. 로봇은 빈 칸(.로 표시)과 컨베이어 위에서만 걸을 수 있다. 격자의 첫 행, 마지막 행, 첫 열, 마지막 열은 벽(W로 표시)으로 이루어져 있고, 다른 칸에도 벽이 있을 수 있다.

컨베이어는 로봇을 특정 방향으로 움직이게 하며, 왼쪽, 오른쪽, 위, 아래를 각각 L, R, U, D로 나타낸다. 로봇은 컨베이어 위에서는 스스로 움직일 수 없다. 컨베이어 위에서 로봇이 영원히 갇힐 수도 있다.

카메라(C로 표시)는 상하좌우 네 방향을 볼 수 있지만 벽을 통해서는 볼 수 없다. 로봇이 카메라와 같은 칸에 있거나 빈 칸 위에서 카메라에 보이면 잡힌다. 컨베이어는 약간 높아서 로봇이 컨베이어 위에 있을 때는 잡히지 않지만, 카메라는 컨베이어 건너편의 빈 칸을 볼 수 있다.

로봇은 S로 표시된 칸에서 시작한다. 출구는 빈 칸 어디에나 있을 수 있다. 각 빈 칸마다 로봇이 잡히지 않고 그곳으로 이동하는 데 필요한 최소 걸음 수를 구하거나, 이동이 불가능한지 판별한다. 한 걸음은 상하좌우로 한 번 움직이는 것이다. 컨베이어에 의해 움직이는 것은 걸음으로 세지 않는다.

입력의 첫 줄에는 두 정수 N과 M이 주어진다. (4 ≤ N, M ≤ 100) 그다음 N개의 줄에는 각각 M개의 문자가 주어지며, 각 문자는 W, ., C, S, L, R, U, D 중 하나이다.

S 문자는 정확히 하나, . 문자는 적어도 하나 있다. 모든 행과 열의 첫 문자와 마지막 문자는 W이다.

배점 15점 중 5점에 대해서는 카메라와 컨베이어가 없다.

추가로 배점 15점 중 5점에 대해서는 컨베이어가 없다.

각 빈 칸마다 한 줄에 정수 하나를 출력한다. 이는 로봇이 잡히지 않고 그 빈 칸으로 이동하는 데 필요한 최소 걸음 수이며, 이동이 불가능하면 −1이다.

출력은 행 우선 순서로, 입력을 위에서 아래로 한 줄씩 읽고 각 줄에서 왼쪽에서 오른쪽으로 읽을 때 만나는 빈 칸의 순서이다. 행 우선 순서 출력의 예는 샘플 출력을 참고한다.