Description

You are on a secret mission, but you get trapped in a 3D underground prison. The mission is timed, and you need to escape from the dungeon in the shortest possible time to continue your task. The dungeon has several levels. Each level is an $R$ by $C$ rectangular grid. When a cell is not occupied by rock, you may move from your current cell to one of the six adjacent cells: front, back, left, right, the cell on the level above, or the cell on the level below. Each move to an adjacent cell takes 1 minute.

Can you escape from the dungeon? If so, what is the minimal time required?

It is said that an artifact is hidden at the exit.

Input Format

The first line contains $L,R,C$ ($L$ is the number of levels, $R$ is the number of rows per level, and $C$ is the number of columns per level, where $1 \leq L,R,C \leq 30$).

Starting from the second line, the layouts of the $L$ levels are given. Each level has $R$ lines, and each line has $C$ cells. There is a blank line between two consecutive levels.

In the input, S marks your starting position, E marks the exit, # means the cell is blocked by rock, and . means the cell is empty.

Output Format

Output exactly one line. If you can reach the exit, print: Escaped in x minute(s).

Here, $x$ is the minimal time you spend. Otherwise, print Trapped!.

3 4 5
S....
.###.
.##..
###.#

#####
#####
##.##
##...

#####
#####
#.###
####E

Escaped in 11 minute(s).

Hint

Source: POJ 2251.

Translated by ChatGPT 5