31328번 - Maze in a Forest 다국어인터랙티브

문제

In this interactive problem, you have to get from the entry of an unknown maze to its exit spending not too much time.

The famous warrior Malcolm, The Hero of Arcania, walked at night through a dark forest. He walked for a long time and started to think he got lost, but suddenly ran into a stone wall on his path. The markings on the stone plate which were visible under fallen leaves clearly indicated that he discovered a maze of dwarven origin.

The hero knows little about the forest and the trees growing there. On the bright side, he spent much time in the company of dwarves, so now he can tell a lot about a maze by just looking at its markings.

The markings on this maze form the characters "SK3". Character "S" means that the maze is a square, that is, the floor of the maze consists of $n \times n$ square cells of size 1ドル \times 1$ meters each. There is a thin solid wall around these cells with two openings. The first one is the entrance near which the hero stands. It is located in the southern wall of the southwestern corner cell of the maze. The second opening is the exit located in the northern wall of the northeastern corner cell of the maze.

Each two cells of the maze sharing a side can be either connected by a passage or separated by a section of a thin inner wall, one meter long. In the maze, from each cell, one can move into any cell sharing a side with it if there is no wall between these cells. Additionally, one can freely move through the exit. The entrance is open only until the hero steps inside the maze. After that, it is immediately closed and opens again only when the hero arrives safely at the exit.

Characters "K3" tell to an experienced maze walker that the maze has the following structure. First, from all possible sections of thin inner walls (there are $n \times (n - 1)$ north-to-south sections in total, and just as many east-to-west sections), one third is selected at random (a non-integer number is rounded down) and considered in a random fixed order. Then, the sections are placed into the maze in that order. If some section would divide the square containing the maze into disconnected parts if it was placed, such section is discarded (not placed). Thus it is guaranteed that the resulting maze will be connected.

Malcolm became happy: he knows so much about the maze that he could certainly arrive at the exit. His goal is to start at the cell of the forest adjacent to the maze entrance and come to the cell of the forest adjacent to the maze exit. Besides, he should hurry: the person who travels from the entrance to the exit fast enough will see the treasure hidden in the forest near the exit. Of course, the above statement is true only if no one got to the treasure earlier.

On second thought, there is something to worry about. Firstly, Malcolm does not know the size of the maze: the length of the square side $n$ can be any integer amount of meters from 10ドル$ to 200ドル$. Secondly, the maze is as dark as the forest around it, so Malcolm has to move almost blindly. At the start of each step, the hero chooses one of four main directions: north, east, south or west. Then he tries to move by one meter in that direction. If the hero runs into an obstacle, he remains where he was. Otherwise, he moves to the neighboring cell in the selected direction. The time required for each step does not depend on the result of the step, so what matters is the total number of steps.

Help the hero to move in such a way that he arrives at the required cell fast enough. The solution will be considered correct if the hero makes at most 5ドル \cdot n + 300$ steps and arrives at the cell outside of the maze exit.

프로토콜

In this problem, the jury program reacts on the commands that a solution issues to the standard output. Each command determines Malcolm's next step. A command is written on a separate line and consists of one capital English letter: "N" for stepping to the North, "E" for stepping to the East, "S" for stepping to the South и "W" for stepping to the West.

For each issued command, the jury program immediately responds with a line passed to the solution's standard input which contains one word written in lowercase English letters: "no" if an obstacle denied the passage, "ok" if the step succeeded, but the hero did not arrive at the target cell, and "end" if the step succeeded and the hero found himself at the target cell. After recieving "end" as a response, the solution must terminate without any further output.

To prevent output buffering, flush the output buffer after each command you issue: this can be done by using, for example, fflush(stdout) in C or C++, System.out.flush() in Java, flush(output) in Pascal or sys.stdout.flush() in Python.

In each test, the maze is fixed in advance after being randomly generated.

If a solution made at least 100ドル,000円$ steps, but did not yet exceed the time limit and did not arrive at the target cell, testing is terminated with "Wrong Answer" outcome.

입력

출력

제한

힌트

예제

예제 설명

The picture above shows the maze which is generated in the first test. Malcolm starts at the cell labeled with a circle and has to arrive at the cell labeled with a cross. This maze can be passed, for example, using the following sequence of commands (below the commands are the results of their execution):

On the picture, this solution is shown by a thick gray line.