捷克理工大学历史悠久——你可能已经知道它在 2007 年庆祝了建校 300 周年。大学的一些建筑同样历史悠久。在老建筑中导航有时会有些棘手，因为那些奇怪的长走廊会在绝对意想不到的地方分叉和汇合。

这导致一些一年级新生在寻找教室时经常遇到困难。因此，学生会开发了一款电脑游戏来帮助学生练习他们的方向感。游戏的目的是找到走出迷宫的路。你的任务是编写一个求解该游戏的验证软件。

迷宫是一个二维的方格网格，每个方格要么是空地，要么是墙。一些空地方格可能包含门或钥匙。有四种不同类型的钥匙和门：蓝色、黄色、红色和绿色。每种钥匙只能打开相同颜色的门。

你可以在相邻的空地方格之间水平或垂直移动，不允许对角线移动。你不能穿过墙壁，也不能离开迷宫区域。如果一个方格包含一扇门，只有当你之前走过含有相应钥匙的方格时，你才能进入该方格。

输入格式

输入包含多张地图。每张地图以包含两个整数 $R$ 和 $C$（$1 \le R, C \le 100$）的一行开始，表示地图的大小。接下来有 $R$ 行，每行包含 $C$ 个字符。每个字符是以下之一：

请注意，允许出现以下情况：

• 多个出口，
• 完全没有出口，
• 相同颜色的多个门和/或钥匙，
• 有钥匙但没有对应的门，反之亦然。

你可以假设你的位置标记（“*”）在每张地图中恰好出现一次。

每张地图后面有一个空行。输入以两个零（代表地图大小）结束。

输出格式

对于每张地图，输出一行，包含句子 “Escape possible in S steps.”，其中 $S$ 是到达任意出口所需的最少步数。如果无法到达任何出口，则输出字符串 “The poor student is trapped!”。

一步定义为在两个相邻格子之间的移动。捡起钥匙或解锁门不计入步数。

样例

输入样例 1

1 10
*........X

1 3
*#X

3 20
####################
#XY.gBr.*.Rb.G.GG.y#
####################

0 0

输出样例 1

Escape possible in 9 steps.
The poor student is trapped!
Escape possible in 45 steps.