Right-Hand Rule

A common way to explore a garden maze is to place your hand on the wall immediately to the right of the entrance as you step in, then walk forward while always keeping that right hand in contact with a wall. This is the right-hand rule.

It is well known that this technique lets you get through a maze that has a single entrance and a single exit, but it does not always succeed for mazes where you must reach a goal somewhere inside the maze.

Read a maze marked with one goal and one or more entrances, and decide whether the right-hand rule finds the goal. Starting at an entrance, keep your right hand on the wall and walk until either the goal is found, or the rule leads you back out of the maze through one of the entrances.

People look around as they walk, so the goal counts as found if you step directly onto it, or if you ever reach a cell that has an unobstructed straight-line view of the goal along a row or a column (no wall lies between you and the goal).

The input contains one or more mazes. Each maze starts with a line holding two integers, $w$ and $h$: the width and the height of the maze. Input ends when either value is less than $3$.

This line is followed by $h$ lines. In each of these lines only the first $w$ characters matter; if a line is shorter than $w$ characters, treat the missing characters as X.

Each character means:

• (space) — an open cell
• G — an open cell that is the goal; every maze has exactly one
• X — a wall
• E — an open cell that is an entrance; every entrance lies on the outer border (as defined by $w$ and $h$), and no two entrances are adjacent

Every maze is completely enclosed by X and E characters.

For each maze, print one line:

The goal would be found from ? out of ? entrances.

Replace the first ? with the number of entrances from which the right-hand rule finds the goal, and the second ? with the total number of entrances.