고립된 로봇

성간 우주선의 잔해 속에 로봇 한 대가 갇혀 있다. 잔해 어딘가에 로봇을 안전한 곳으로 옮겨 줄 순간이동 장치가 있다.

우주선은 모든 축을 따라 통제를 잃고 회전하고 있다. 근처의 태양이 잔해에 빛을 비춘다. 우주선에는 인공 중력 발생기도 있다. 인공 중력은 우주선의 방향과 관계없이 항상 로봇을 태양에서 멀어지는 쪽으로 당긴다.

로봇은 태양광 패널을 달고 있어서, 잔해 사이를 움직이려면 태양광 전력에 의존해야 한다. 잔해가 햇빛을 가리면 로봇은 움직이지 못한다. 로봇은 매번 이동한 뒤 스스로를 고정하므로, 허우적거리거나 우주 공간으로 떨어지지 않는다.

잔해와 그 주변은 크기 $m \times n \times p$의 3차원 격자 $a$로 표현된다. 각 칸은 우주선의 일부이거나 진공이다. 우주선의 칸들은 서로 연결되어 있지 않을 수도 있다.

로봇은 처음에 우주선의 한 부분에 고정되어 있다. 언제 움직이고 언제 편한 방향에서 태양이 비출 때까지 기다릴지는 로봇이 스스로 정한다.

중력은 3개 축 각각의 양 방향 중 하나, 총 6방향 중 하나로 로봇을 당길 수 있다. 어떤 칸에서 태양 반대 방향으로 잔해가 없으면 그 칸은 태양빛을 받는다. 이동하기 전에 로봇은 중력이 당기는 방향을 고를 수 있다. 이동할 때는 출발 칸과 도착 칸이 동시에 햇빛을 받아야 한다.

다음 이동이 허용된다. 그림에서 빛은 항상 위에서 비춘다. 진한 파란 칸은 로봇이고, 밝은 주황 칸은 이동할 수 있는 도착 칸이다.

1. 바닥을 따라 이동

로봇이 어떤 블록 위에 놓여 있으면, 같은 높이의 인접한 칸으로 이동할 수 있다. 대각선으로는 이동할 수 없다. 도착 칸도 태양빛을 받아야 한다.

2. 절벽에서 뛰어내리기

로봇은 높은 위치에서 한 걸음 내디딘 뒤 아래로 떨어질 수 있다. 떨어지는 거리에는 제한이 없다.

로봇은 우주 공간의 빈 곳이나 빛이 들지 않는 위치로 떨어질 수 없다.

3. 아래로 떨어지기

로봇이 태양빛을 받으면서 매달린 상태가 되면 아래로 떨어질 수 있다. 중력 방향이 바뀌었을 때 이런 상황이 생길 수 있다.

로봇은 우주 공간의 빈 곳으로 떨어질 수 없다.

목표는 가능하다면 가장 적은 이동 횟수로 순간이동 장치에 도달하는 것이다. 순간이동 장치가 작동하려면 로봇이 우주선에 단단히 고정되어 있어야 한다. 즉, 로봇은 유효한 이동이 끝난 시점에 순간이동 장치 위치에 있어야 하며, 순간이동 장치를 통과하며 떨어지는 것은 인정되지 않는다. 순간이동 장치는 태양빛이나 로봇의 이동을 막지 않는다.

첫 줄에는 세 정수 $m$, $n$, $p$가 주어진다 ($1 \le m, n, p \le 500$).

우주선과 그 주변은 $p$개의 블록으로 설명된다. $k$번째 블록은 높이 $k$의 층을 나타낸다. 각 블록은 $n$줄로 이루어지며, 블록의 $i$번째 줄은 $m$개의 문자로 되어 있다. $j$번째 문자가 $a_{ijk}$이다.

• *는 꽉 찬 블록이다.
• -는 빈 블록이다.
• R은 로봇이 있는 블록이다. 이런 블록은 하나뿐이다.
• T는 순간이동 장치가 있는 블록이다. 이런 블록은 하나뿐이다.

로봇은 항상 꽉 찬 블록과 연결되어 있다고 보장된다.

순간이동 장치에 도달하는 데 필요한 최소 이동 횟수를 출력한다. 도달할 수 없으면 -1을 출력한다.