Description

Worm is a classic computer game with many versions, but they all share a common rule: you control a worm that turns on the screen and try to avoid colliding with itself or with obstacles.

Here we simulate a simple version. The game is played on a $50 \times 50$ board, with the top-left corner at $(1, 1)$. Initially, the worm occupies a chain of $20$ connected cells. “Connected” means adjacent horizontally or vertically. The worm starts stretched horizontally from $(25, 11)$ to $(25, 30)$, where $(25, 30)$ is its head. The worm can move only East \verb!E!, West \verb!W!, South \verb!S!, and North \verb!N!, but it cannot move into itself, so moving West \verb!W! at the very beginning is not allowed. On each move, the worm moves one cell in the given direction and keeps its length unchanged. Therefore, only the cells occupied by the head and the tail change after one step. Note: the head may move into the cell just vacated by the tail.

You are given a sequence of move instructions and must simulate the worm’s movement until the worm runs into itself, the worm goes off the board, or the worm successfully completes all the instructions. In the first two cases, you should ignore any remaining instructions.

Description

Input Format

Each input file contains multiple test cases, each taking two lines.

The first line is an integer $n\ (n<100)$, the number of move instructions (with $n=0$ indicating the end of input).

The second line contains $n$ characters, each one of \verb!ESWN!, with no spaces, representing the move instructions.

Output Format

For each test case, output one line, in one of the following $3$ formats:

• \texttt{The worm ran into itself on move \textrm{\it m}.}
• \texttt{The worm ran off the board on move \textrm{\it m}.}
• \texttt{The worm successfully made all \textrm{\it m} moves.}

Here, $m$ is the step number you must determine.

18 
NWWWWWWWWWWSESSSWS 
20 
SSSWWNENNNNNWWWWSSSS 
30 
EEEEEEEEEEEEEEEEEEEEEEEEEEEEEE 
13 
SWWWWWWWWWNEE 
0

The worm successfully made all 18 moves. 
The worm ran into itself on move 9. 
The worm ran off the board on move 21. 
The worm successfully made all 13 moves.

Hint

Translated by ChatGPT 5