Key Task

You are trapped in a labyrinth and must find your way out.

The labyrinth is a two-dimensional grid of square cells. Every cell is either free or filled with a wall. Some free cells contain a door or a key. There are four colors of keys and doors: blue, yellow, red, and green. A key opens only doors of its own color.

You may move between horizontally or vertically adjacent free cells; diagonal moves are not allowed. You may not move through walls and you may not leave the grid. You may enter a cell that holds a door only if you have already stepped on a cell holding a key of the same color. A key you step on is kept for the rest of that map.

The input contains several maps.

Each map starts with a line containing two integers R and C (1 ≤ R, C ≤ 100), the number of rows and columns. The next R lines each contain exactly C characters describing the map. Each character is one of:

A map may have more than one exit, or no exit at all. It may contain several doors or keys of the same color, keys without a matching door, and doors without a matching key. The starting position * appears exactly once in every map.

Each map is followed by one blank line. The input ends with a line containing two zeros in place of R and C; that line is not a map.

For each map, print one line.

If an exit can be reached, print Escape possible in S steps., where S is the minimum number of steps needed to reach any exit.

If no exit can be reached, print The poor student is trapped! instead.

One step is a move between two adjacent cells. Picking up a key or opening a door does not count as a step.