The Wire Ghost

Žofka is bending a copper wire. She starts with a straight wire placed on the table with the starting point glued to the middle of the table. She then repeatedly picks a point on the wire and bends the part starting at that point (away from the starting point) by $90$ degrees (either clockwise or counterclockwise). Throughout the process the starting point stays glued to the middle of the table.

The most important consideration is that she does not want the wire to touch itself as she bends it (that would summon the wire ghost). She needs your help. She has a list of points together with the direction at each point (clockwise or counterclockwise). She wants to know if bending the wire at the listed points in the given order would cause the wire ghost to appear at any time during the process.

The first line contains two integers $L$ and $n$ where $L$ is the length of the wire and
$n$ is the number of
points. Each of the next $n$ lines contains a number from
$\{ 0,\dots ,L\} $
(describing the point on the wire) followed by `W` (clockwise) or `C` (counter
clockwise). You may assume $L\leq
100\, 000\, 000$ and $n\leq 1\, 000$.

The output consists of a single line consisting of the
string `GHOST` if the wire would touch itself
during the bending, and the string `SAFE`
otherwise.

Sample Input 1 | Sample Output 1 |
---|---|

4 3 3 C 2 C 1 C |
GHOST |

Sample Input 2 | Sample Output 2 |
---|---|

3 3 1 C 2 C 3 C |
SAFE |