描述

“算了吧，” 加勒特抱怨道，把他的 PlayStation VIII 游戏手柄扔到一边，“这一关根本过不去。” 他刚刚在游戏《旅鼠$9$：迷失太空》的第 $54$关 “死” 了第 $17$ 次。

“不是的，” 他的弟弟费雷特回应道，“我可以证明。” 费雷特从他的李维斯 Huggies 牛仔裤后兜掏出了他的 PlaySkool 掌上电脑。

“首先，把这一关想象成一个矩形网格。” 费雷特按了几下掌上电脑上的几个按钮，就出现了一个他所描述的矩形。“你的角色，一只拿着雨伞的旅鼠，从这个矩形的顶部开始。它的目标是在不死亡的情况下到达底部。”

“我知道，你这个讨厌鬼，但那些激光枪怎么办呢？” 加勒特抱怨道。

“我叫费雷特，我正要说这个呢。如果我们把这一关表示为一个矩形网格，那么旅鼠可以占据一个方格，每把激光枪也可以占据一个方格。记住，激光枪是循环发射的：它们在第一轮都向上射击，第二轮向右射击，第三轮向下射击，第四轮向左射击，然后重复这个顺序。”

“但你忘了那些熔岩坑了！” 加勒特叫道。

“你都没让我说完。每个熔岩坑也占据一个方格。而且每一块草地，也就是旅鼠的目的地，同样占据一个方格。然后，就只需要在一系列的回合中操控旅鼠和激光束，来判断旅鼠是否有可能在不 ‘死亡’ 的情况下到达底部了。”

“你觉得你很聪明啊，费雷特，那你再给我清清楚楚、简明扼要地解释一遍试试。”

“当然可以”：

这一关将由一个方格网格组成。每道激光束和旅鼠的移动方式可以用 “回合” 来描述。为了判断旅鼠能否在不死亡的情况下到达这一关的底部，费雷特制定了一些规则：

1. 每个回合由两个步骤组成：
   • 首先，激光枪会 “开火”，并一直保持到回合结束，激光束的方向取决于回合数。在第一个回合，每把激光枪会向上射击（每把激光枪正上方的所有方格都是 “不安全” 的，旅鼠不能占据这些方格）；在第二个回合，每把激光枪会向右射击；在第三个回合，每把激光枪会向下射击；在第四个回合，每把激光枪会向左射击；在第五个回合，这个顺序会重复。 例如：

    列
    01234
R 0|  L  |<- 旅鼠总是从第 0 行的某一列开始
o 1|     | 在这个例子中，在第一个回合，激光束
w 2|   S | 会占据方格 (3,0)、(3,1)；第二个回合，$(4,2)；
  3|     | 第三个回合，(3,3)、(3,4)、(3,5)、(3,6)；第四个回合， 
  4|     | (0,2)、(1,2)、(2,2)；第五个回合（重复），(3,0)、(3,1) 等等。  
  5|     | （方格用 (列,行) 的表示方法）
  6|GPPGG|<- 熔岩坑和草地方格总是在最后一行

- 其次，旅鼠总是向下移动一行，但可以移动到三列中的任意一列：向左一列、向右一列，或者留在同一列。在上面的例子中，在第一个回合，旅鼠$（L）$可以移动到方格 $(1,1)、(2,1) $或 $(3,1)$（不过，如果它移动到 $(3,1)$，就会因为激光束而死亡）。然而，在任何一个回合中，旅鼠都不能移出网格（也就是说，它不能移动到$ -1 $列，或者移动到列数等于总列数的列）。

2. 如果旅鼠在一系列回合后能够安全到达最后一行的任何一个 “草地” 方格而不死亡，那么这一关就被认为是 “可能通过的”。
3. 如果旅鼠在任何时候占据了与激光枪、激光束或熔岩坑相同的方格，它就会死亡。这包括：
   • 旅鼠移动到熔岩坑占据的方格。
   • 旅鼠移动到激光枪占据的方格。
   • 旅鼠移动到激光束占据的方格（即使那是一个草地方格！）。
   • 激光枪向旅鼠所在的方格发射激光束。

输入

这个问题的输入将由一系列（非空）最多 $100$个数据集组成。每个数据集将按照以下描述进行格式化，并且数据集之间不会有空白行。每个数据集将描述这一关的初始条件。单个数据集包含以下部分：

1. 起始行 —— 一行内容为 “START x y”，其中 $0 < x < 10$，$x$ 是表示这一关的网格的列数，$1 < y < 10$，$y$ 是表示这一关的网格的行数。
2. 接下来的$y$行将表示这一关的各行，从第$0$ 行（顶部）开始。每行将由 $x$ 个字母组成。这些字母将表示这一关的组成部分，如下所示：
   • $L$ —— 旅鼠（每个数据集中只有一个 ‘L’，并且它总是在第 0 行）
   • $S$ —— 激光枪（这些方格永远不会在最后一行）
   • $P$ —— 熔岩坑（这些方格总是在最后一行）
   • $G$ —— 草地（这些方格也总是在最后一行）
   • $O$ —— “空” 的空气方格
3. 结束行 —— 一行内容为 “END”。

在最后一个数据集之后将有一行内容为 “ENDOFINPUT”。

输出

每个数据集的输出将恰好是一行。这一行要么是 “FERRET”，要么是 “GARRET”（全部大写，前后没有空白字符）。

如果旅鼠能够在一系列回合后安全（不死亡）到达这一关底部的任何一个草地方格，就输出 “FERRET”。

如果一个数据集不满足输出 “FERRET” 的条件，就输出 “GARRET”。

输入示例

START 5 7
OOLOO
OOOOO
OOOSO
OOOOO
OOOOO
OOOOO
GPPGG
END
START 3 3
OLO
OSO
GGG
END
START 5 8
LOOOS
OOOOO
OOOOO
OOOOO
OOOOO
OOOOO
OOOOO
PPPPG
END
ENDOFINPUT

输出示例

FERRET
GARRET
GARRET

来源

美国中南部 2002 年