cho.sh

우산 문제

아직 제출이 없습니다시간 제한1초메모리 제한128 MB

문제

개럿이 컨트롤러를 내던졌다. "됐어, 이 스테이지는 못 깨." 게임 "레밍즈 9: 로스트 인 스페이스"의 54번째 스테이지에서 열일곱 번째로 죽은 참이었다.

동생 페럿이 받아쳤다. "깰 수 있어. 증명해 줄게." 페럿은 주머니에서 PDA를 꺼냈다.

"먼저 스테이지를 직사각형 격자라고 생각해. 우산을 든 레밍은 격자 맨 윗줄에서 출발해서, 죽지 않고 맨 아랫줄까지 내려가야 해."

"그건 나도 알아. 레이저포는 어쩌고?" 개럿이 투덜댔다.

"내 이름은 페럿이고, 지금 말하려던 참이야. 격자에서 레밍이 한 칸을 차지하고, 레이저포도 한 칸씩 차지해. 레이저포는 방향을 돌려 가며 쏴. 첫 턴에는 위, 둘째 턴에는 오른쪽, 셋째 턴에는 아래, 넷째 턴에는 왼쪽, 그다음엔 다시 이 순서를 반복해."

"용암 구덩이는 빼먹었잖아!"

"아직 안 끝났어. 용암 구덩이도 한 칸씩 차지하고, 레밍이 도착해야 할 잔디도 한 칸씩 차지해. 그러면 턴마다 레밍과 레이저 빔을 움직여 보면서 레밍이 죽지 않고 맨 아래까지 갈 수 있는지 따지면 돼."

"그렇게 잘났으면 알아듣게 다시 정리해 봐."

"그러지 뭐."

스테이지는 정사각형 칸으로 이루어진 격자다. 레밍과 레이저 빔의 움직임은 턴으로 나타내고, 한 턴은 두 단계로 이루어진다.

  1. 먼저 모든 레이저포가 빔을 쏘고, 그 빔은 턴이 끝날 때까지 남아 있다. 방향은 턴 번호로 정해진다. 1턴에는 위, 2턴에는 오른쪽, 3턴에는 아래, 4턴에는 왼쪽으로 쏘고, 5턴부터는 이 순서를 반복한다. 빔은 레이저포가 있는 칸에서 그 방향으로 격자 끝까지 뻗고, 빔이 지나가는 칸은 모두 위험하다.
  2. 그다음 레밍이 한 줄 아래로 내려간다. 열은 왼쪽으로 한 칸, 오른쪽으로 한 칸, 그대로 중에서 하나를 고른다. 격자 밖으로는 나갈 수 없어서 -1번 열이나 열 개수와 같은 번호의 열로는 갈 수 없다.

아래 격자를 보자. 칸은 (열, 줄)로 적고, 위쪽 숫자가 열 번호, 오른쪽 숫자가 줄 번호다.

 01234
|  L  | 0
|     | 1
|   S | 2
|     | 3
|     | 4
|     | 5
|GPPGG| 6

레밍은 항상 0번 줄에서 출발하고, 용암 구덩이와 잔디는 항상 마지막 줄에 있다. 레이저포는 (3, 2)에 있다. 1턴 빔은 (3, 1)과 (3, 0)을, 2턴 빔은 (4, 2)를, 3턴 빔은 (3, 3), (3, 4), (3, 5), (3, 6)을, 4턴 빔은 (2, 2), (1, 2), (0, 2)를 덮는다. 5턴 빔은 다시 1턴과 같다. 1턴에 레밍은 (1, 1), (2, 1), (3, 1) 중 한 칸으로 내려갈 수 있는데, (3, 1)로 가면 빔에 맞아 죽는다.

레밍은 다음 네 경우에 죽는다.

  1. 용암 구덩이가 있는 칸으로 이동한다.
  2. 레이저포가 있는 칸으로 이동한다.
  3. 빔이 지나가는 칸으로 이동한다. 그 칸이 잔디여도 죽는다.
  4. 레밍이 서 있는 칸으로 빔이 들어온다. 0번 줄에 서서 1턴 빔을 맞는 경우도 여기에 들어간다.

레밍이 죽지 않고 맨 아랫줄의 잔디 칸에 도착하면 그 스테이지는 깰 수 있다.

입력

입력은 데이터 집합이 하나 이상 100개 이하로 이어진 형태이고, 집합 사이에 빈 줄은 없다. 각 데이터 집합은 스테이지의 시작 상태를 나타내며 다음과 같이 이루어진다.

  1. 시작 줄: START x y 한 줄. xx는 격자의 열 개수로 0<x<100 < x < 10이고, yy는 격자의 줄 개수로 1<y<101 < y < 10이다.
  2. 이어지는 yy개의 줄은 격자의 0번 줄(맨 위)부터 차례로 나타내고, 각 줄은 xx개의 문자로 이루어진다. 문자의 뜻은 다음과 같다.
    • L: 레밍. 데이터 집합마다 하나뿐이고 항상 0번 줄에 있다.
    • S: 레이저포. 마지막 줄에는 나오지 않는다.
    • P: 용암 구덩이. 항상 마지막 줄에 있다.
    • G: 잔디. 항상 마지막 줄에 있다.
    • O: 빈 칸.
  3. 끝 줄: END 한 줄.

마지막 데이터 집합 다음에는 ENDOFINPUT만 적힌 줄이 하나 온다.

출력

데이터 집합마다 정확히 한 줄을 출력한다. 레밍이 죽지 않고 맨 아랫줄의 잔디 칸에 도착할 수 있으면 FERRET을, 그러지 못하면 GARRET을 출력한다. 두 단어 모두 대문자로만 쓰고 앞뒤에 공백을 붙이지 않는다.