G. Ghost Gym
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

Cindy is playing a so-called "Kaizo" ROMHack of Pokémon Crystal, meaning that fans had modified the game to massively increase the difficulty to infuriating (unfair?) levels. For some modders, this can include not just the Pokémon battles, but also the overworld puzzles.

The Ghost Gym in Ecruteak city has a puzzle which goes as follows (slightly modified for simplicity).

  • There is an $$$r \times c$$$ map that you must traverse. Your character starts at the top-left-most square, and must traverse to the bottom-right-most square.
  • In one move, your character may take a single step north, south, east, or west.
  • Each tile in the map is flagged as either SAFE or TRAP.
    • If you step on a TRAP tile, you are immediately teleported back to your starting position at the top-left corner!
    • If you exit the bounds of the grid, you are also immediately teleported back to your starting position.
    • It is guaranteed that the top-left-most and bottom-right-most squares are SAFE
  • You do not know which tiles are safe, and which ones are trapped!
Then, the challenge is simple—make it to the bottom right corner, or shout RIGGED if the task is impossible.

Of course, the "maze" in the base game is very simple, but the Kaizo modders have gone out of their way to make their maze as painful as possible. Cindy has been attempting this for hours and is starting to get tilted. She asks you if it's possible to develop a program that can solve this problem for her.

Interaction

The judge first outputs two space-separated integers $$$r$$$ and $$$c$$$, the dimensions of the grid.

Then, you can now move around the grid. You can make statements to the judge:

  • You can output one of N or S or E or W in order to move one step north, south, east, or west, respectively. The judge then responds with one of:
    • YAY if the tile you stepped on is the bottom-right corner.
      • You pass the test case!
      • The judge will send no further messages and your program should terminate.
    • SAFE if the tile you stepped on is SAFE (and not the destination); nothing more happens.
    • TRAP if the tile you stepped on is a TRAP, or if you exited the bounds of the grid; your character is immediately teleported back to the top-left corner before your next move.
  • At any point, you can output RIGGED to declare that you think it's impossible to reach the bottom-right-most corner.
    • If you are correct, then you pass this test case.
    • If you are incorrect, then you get a Wrong Answer for this test case.
    • In either case, the judge will send no further messages and your program should terminate.
If you try to take more than $$$10^5$$$ steps, the judge will output TIMES UP and then send no further messages.
Scoring

$$$$$$\begin{align*}

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 2 \leq r, c \leq 20 \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{35} & r = c = 2 \\ \hline 2 & \mathbf{20} & r, c \leq 5 \\ \hline 3 & \mathbf{20} & \text{It is possible, and all }\mathtt{OKAY}\text{ squares lie on \\ the unique shortest path from start to finish.} \\ \hline 2 & \mathbf{25} & \text{No further constraints.} \\ \hline \end{array}\\

\end{align*}$$$$$$

Note

Here is a sample interaction. We also provide the map, with safe squares colored lilac, and traps colored a deep indigo. The interaction corresponds to the following steps on the map—stepping on a trap (and being sent back to the start) is represented by the red exclamation point. We remind you that the contestant does not have access to this map—it's only provided to you here to help understand the sample. 


Judge       Contestant
4 6
            S
SAFE
            S
TRAP
            S
SAFE
            E
SAFE
            E
SAFE
            E
TRAP
            S
SAFE
            E
SAFE
            E
SAFE
            N
SAFE
            E
SAFE
            E
SAFE
            E
SAFE
            S
SAFE
            S
SAFE
            S
YAY

Here is another sample interaction. Here, the map is not solvable, so the contestant is correct for saying the game is RIGGED 

Judge       Contestant
3 3
            S
TRAP
            E
TRAP
            RIGGED