Problem T
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.

Input

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$.

Output

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.

4 3
3 C
2 C
1 C

GHOST

3 3
1 C
2 C
3 C

SAFE