/*
 * Lemming.java
 *
 * Created on August 16, 2002, 10:02 AM
 */
import java.io.*;
import java.util.*;
/**
 *  This class is used to simulate a lemmings game.
 *  Proper use:
 *      lemmingGame = new LemmingGame( char[][], width, height );
 *      lemmingGame.start(); 
 *
 *  char[][] is a two dimensional char array populated with the lemming data
 *  width is the width of the two dimensional array
 *  height is the height of the two dimensional array
 *
 * @author  andrewm
 */
public class Lemming
{
    // Static constant strings
    public static final String START		= "START";
    public static final String END			= "END";  
	public static final String END_OF_INPUT = "ENDOFINPUT";
    public static final String WIN			= "FERRET";
    public static final String LOSE			= "GARRET";
    
    // Static constant characters
    public static final char LEMMING = 'L';
    public static final char LASER   = 'S';
    public static final char OPEN    = 'O';
    public static final char GRASS   = 'G';
    public static final char PIT     = 'P';
    
    // Static constant bytes representing laser directions
    public static final byte UP =    0;
    public static final byte RIGHT = 1;
    public static final byte DOWN =  2;
    public static final byte LEFT =  3;
    
    // Static constant bytes representing lemming movement directions
    public static final byte DOWN_LEFT = 0;
    public static final byte DOWN_STRAIGHT = 1;
    public static final byte DOWN_RIGHT = 2;
    
    // two dimensional array used for gameboard
    private char[][] map;
    
    // dimensions of the game board
    private int width;
    private int height;
    
    // starting position of the lemming
    private int row;
    private int col;
    
    // current turn number
    private int turn = 0;
    
    // vector used to keep track of bad paths
    private Vector badPaths = new Vector();
    
    /** 
     *  Creates a new instance of Lemming 
     *  
     *  @param _map Two dimension array used for the game board
     *  @param _width The width of the map
     *  @param _height The height of the map
     */
    public Lemming( char[][] _map, int _width, int _height )
    {
        map = _map;
        width = _width;
        height = _height;
    }
    
    /**
     *  This method is used to start the recursive path finding algorithm
     */
    public void start()
    {
        // find the initial starting position of the lemming
        findLemming();
        
        // try moving down and left, then down, then down and right.
        // keep doing this recursively until a path is found.
        if( !move( DOWN_LEFT, this.row, this.col, this.turn ) )
        {
            if( !move( DOWN_STRAIGHT, this.row, this.col, this.turn ) )
            {
                if ( !move( DOWN_RIGHT, this.row, this.col, this.turn ) )
                {
                    System.out.println( LOSE );
                    return;
                }
            }
        }
        
        System.out.println( WIN );
    }
    
    /**
     *  This method is used to move the lemming one square.  The method then
     *  recursively calls itself.  It returns if it can't find a safe path.
     *
     *  @param direction The direction that the lemming is going to move
     *  @param row The row that the lemming is in
     *  @param col The column that the lemming is in
     *  @param turn The turn number it is which is used to determine the direction of the laser
     *  @return boolean Returns true if a safe path exists
     */
    private boolean move( byte direction, int row, int col, int turn )
    {
        // First, check to see if the lemming is already being hit by a laser
        if ( hitByLaser( row, col, (byte)( turn % 4 ) ) )
        {
            return false;
        }
        
        // if the direction is down and left or down and right then modify the col accordingly.
        // also, check to see if the movement is within bounds of the arrary
        switch( direction )
        {
            case DOWN_LEFT:
                                if ( col > 0 ) 
                                { col--; }
                                else
                                { return false; }
                                break;
            case DOWN_RIGHT:
                                if ( col < width - 1 )
                                { col++; }
                                else
                                { return false; }
                                break;
        }
        row++;
        
        // check to see if the lemming is hit by a laser or in a pit
        if ( ( hitByLaser( row, col, (byte)( turn % 4 ) ) ) ||
             ( inPit( row, col ) ) )
        {
            return false;
        }
                
        // check to see if the lemming is safely on the grass
        if ( onGrass( row, col ) )
        {
            return true;
        }
        
        // increase the turn number, and try another move
        turn++;
        
        // check to see if this path has already been tried
        if ( badPath( row, col, turn ) )
        {
            return false;
        }
        
        if( !move( DOWN_LEFT, row, col, turn ) )
        {
            if( !move( DOWN_STRAIGHT, row, col, turn ) )
            {
                if ( !move( DOWN_RIGHT, row, col, turn ) )
                {
                    addBadPath( row, col, turn );
                    return false;
                }
            }
        }        
        
        return true;
    }
    
    /**
     *  Finds where the lemming is on the map and sets the row and col member
     *  variables.  This is only used to initially find the lemming.  The lemming
     *  should always be in the first row, but check the whole thing just in case.
     */
    private void findLemming()
    {
        for( int i = 0; i < height; i++ )
        {
            for( int j = 0; j < width; j++ )
            {
                if( map[i][j] == LEMMING )
                {
                    this.row = i;
                    this.col = j;
                    return;
                }
            }
        }
    }
    
    /**
     *  Checks to see if the lemming is hit by a laser.
     *
     *  @param int row The row the lemming is on
     *  @param int col The column the lemming is on
     *  @param direction The current direction the laser is firing
     *  @return boolean Returns true if the lemming is hit by a laser
     */
    private boolean hitByLaser( int row, int col, byte direction )
    {
        switch( direction )
        {
            // if the laser is firing down, the lemming should check above him
            case DOWN :
                        for( int i = row; i >= 0; i-- )
                        {
                            if ( map[i][col] == LASER ) return true;
                        }
                        break;
            // if the laser is firing left, the lemming should check to his right
            case LEFT :
                        for( int i = col; i < width; i++ )
                        {
                            if ( map[row][i] == LASER ) return true;
                        }
                        break;
            // if the laser is firing up, the lemming should check below him                        
            case UP :
                        for( int i = row; i < height; i++ )
                        {
                            if ( map[i][col] == LASER ) return true;
                        }
                        break;
            // if the laser is firing right, the lemming should check to his left                        
            case RIGHT :
                        for( int i = col; i >= 0; i-- )
                        {
                            if ( map[row][i] == LASER ) return true;
                        }
                        break;
        }
        
        return false;
    }
    
    /**
     *  Checks to see if the lemming landed in a pit.
     *
     *  @param row The row the lemming is on
     *  @param col The col the lemming is on
     *  @return boolean returns true if the coordinates are for a pit square
     */
    private boolean inPit( int row, int col )
    {
        return map[row][col] == PIT;
    }
    
    /**
     *  Checks to see if the lemming landed on a grass square.
     *
     *  @param row The row the lemming is on
     *  @param col The column the lemming is on
     *  @return boolean returns true if the coordinates are for a grass square
     */
    private boolean onGrass( int row, int col )
    {
        return map[row][col] == GRASS;
    }
    
    /**
     *  Determins whether the current position has already been marked as a bad path.
     *
     *  @param row The current row that the lemming is on
     *  @param col The current col that the lemming is on
     *  @param turn The current turn number
     *  @return boolean Returns true if the path is in the vector
     */
    private boolean badPath( int row, int col, int turn )
    {
        return badPaths.contains( row + "," + col + "," + turn );
    }
    
    /**
     *  Adds an entry to the bad paths vector to try and reduce redundant attempts
     *  at checking the same path.
     *
     *  @param row The current row the lemming is on
     *  @param col The current column the lemming is on
     *  @param turn The current turn number
     */
    private void addBadPath( int row, int col, int turn )
    {
        String pathElement = row + "," + col + "," + turn;
        
        if( !badPaths.contains( pathElement ) )
        {
            badPaths.add( pathElement );
        }
    }
    
    /**
     *  This method prints out the two dimensional array used for the Lemming game.
     *  This is only used when debugging.
     */
    public void printMap()
    {
        for( int i = 0; i < height; i++ )
        {
            for( int j = 0; j < width; j++ )
            {
                System.out.print( map[i][j] );
            }
            System.out.println();
        }
    }
    
    /**
     * This is the main procedure which gets run from the command line.
     *
     * @param args the command line arguments
     */
    public static void main( String[] args )
    {
        int width;
        int height;
		String token = null;
        String line = null;
        StringTokenizer st = null;
        char[][] map = null;
        Lemming lemmingGame = null;
        
        try
        {
            // create the input stream
            BufferedReader in = new BufferedReader( new InputStreamReader( System.in ) );
            
            // read in a line which should be the start of a data set
            line = in.readLine();
            
            // loop through the entire input stream
            while( ( line != null ) && ( !"".equals( line.trim() ) ) )
            {
                st = new StringTokenizer( line );
                
				token = st.nextToken();
				
                // check to see if this is the start of a data set
                if ( token.equals( START ) )
                {   
                    // read in the width and height of the gameboard
                    width = Integer.parseInt( st.nextToken() );
                    height = Integer.parseInt( st.nextToken() );
                    
                    // create a new two dimensional array
                    map = new char[height][width];
                    
                    // populate each row of the gameboard
                    for( int i = 0; i < height; i++ )
                    {
                        in.read( map[i], 0, width );
                        in.readLine();
                    }
                    
                    // Create a new lemming instance
                    lemmingGame = new Lemming( map, width, height );
                                       
                    // start the lemming game
                    lemmingGame.start();
                    
                    // read in a line which should be the end of the data set
                    line = in.readLine();
                    
                    // check to see if this is the end of the data set
                    if ( line.startsWith( END ) )
                    {
                        // read in the next line after the data set which could
                        // be another data set or the end of the input file
                        line = in.readLine();
                    }
                    else
                    {
                        // inform the user of the invalid end of data set symbol
                        System.out.println( "Invalid end symbol" );
                        break;
                    }
                }
				// check for end of input marker
				else if ( token.equals( END_OF_INPUT ) )
				{
					break;
				}
                else
                {
                    // inform the user of the invalid start of data set symbol
                    System.out.println( "Invalid start symbol" );
                    break;
                }
            }
        }
        catch( IOException ioe )
        {
            ioe.printStackTrace();
        }
        catch( NumberFormatException nfe )
        {
            System.out.println( "Width and Height dimensions must be integers" );
        }
        catch( Exception e )
        {
            e.printStackTrace();
        }
    }
}