Description

In the wreckage of an abandoned spaceship, there is a robot. Somewhere in the wreckage there is a teleporter that can send this poor robot to a safe place.

The spaceship is uncontrollably tumbling in all directions. Light from a nearby star can shine onto the wreckage. The spaceship is equipped with an artificial gravity generator. Artificial gravity always pulls the robot in the direction away from the star, no matter how the ship is oriented.

The robot is equipped with solar panels and must rely on sunlight to move on the wreckage. When some part of the wreckage blocks the light, the robot cannot move. However, after moving, the robot always anchors itself so that it will not be shaken away or fall into space.

The wreckage and the area around it can be represented as a three-dimensional coordinate space of size $m \times n \times p$. Each small cell in the space may be part of the wreckage or vacuum. The spaceship wreckage may be disconnected.

The robot starts anchored on some piece of the ship. The robot can decide when to move or when to wait for light to shine from a suitable direction.

Formally, gravity can act on the robot in six directions: two directions along each of the three coordinate axes. A cell is lit if there is no wreckage blocking it in the direction opposite to gravity. When making a move, both the starting cell and the destination cell must be lit at the same time.

The following moves are available (the light in the figures shines from above; the blue cell is the robot; orange cells are possible destinations):

1. Moving on flat ground
   If the robot is anchored on a block, it can move to a neighboring block at the same height as the starting cell.
   The robot cannot move diagonally. The destination must also be lit.
   

2. Stepping off from a height
   The robot can step out by one cell from a higher place and then fall down. There is no limit on the falling height.
   The robot must not fall into space, and it must not land on an unlit cell.
   

3. Falling
   If the robot is lit and hanging in the air, it can fall down. This may happen after the direction of gravity changes.
   The robot must not fall into space.
   

The robot’s goal is to reach the teleporter. If there are multiple ways, it should use the one with the fewest moves. The teleporter requires the robot to be anchored on the ship in order to work. In other words, the robot must arrive at the teleporter’s cell as the result of some move; merely passing through it while falling does not activate it. The teleporter does not block light and does not obstruct the robot’s movement.

Input Format

The first line contains three integers $m, n, p \ (1 \leq m, n, p \leq 500)$.

The spaceship and the surrounding space are described by $p$ layers.

Layer $k$ describes the cells at height $k$. Each layer contains $n$ rows.

In layer $k$, row $i$ contains $m$ characters describing the cells. Let $a_{ijk}$ denote the $j$-th character.

• If $a_{ijk}$ is *, the cell is wreckage.
• If $a_{ijk}$ is -, the cell is vacuum.
• If $a_{ijk}$ is R, the cell contains the robot. The testdata guarantees there is exactly one robot cell, and the robot is anchored on a wreckage cell.
• If $a_{ijk}$ is T, the cell contains the teleporter. The testdata guarantees there is exactly one teleporter cell.

Output Format

Output the minimum number of moves required to reach the teleporter. If it is impossible, output $-1$.

2 5 1
R-
*-
*-
*T
**

1

3 2 1
R-T
***

2

3 3 1
-R-
-*-
-T-

-1

5 4 2
-R---
-****
-****
-****
-----
-----
*T---
----*

5

Hint

Translated by ChatGPT 5