En este problema interactivo, tienes que ir desde la entrada de un laberinto desconocido hasta su salida sin emplear demasiado tiempo.

El famoso guerrero Malcolm, el héroe de Arcania, caminaba de noche por un bosque oscuro. Llevaba mucho tiempo andando y empezó a pensar que se había perdido, pero de repente se topó con un muro de piedra en su camino. Las marcas de la losa de piedra, visibles bajo las hojas caídas, indicaban claramente que había descubierto un laberinto de origen enano.

El héroe sabe poco del bosque y de los árboles que crecen en él. Por suerte, pasó mucho tiempo en compañía de enanos, así que ahora puede saber mucho sobre un laberinto con solo observar sus marcas.

Las marcas de este laberinto forman los caracteres «SK3». El carácter «S» significa que el laberinto es cuadrado, es decir, que su suelo consta de $n \times n$ celdas cuadradas de $1 \times 1$ metros cada una. Alrededor de estas celdas hay un muro delgado y continuo con dos aberturas. La primera es la entrada, junto a la que está el héroe. Se encuentra en la pared sur de la celda de la esquina suroeste del laberinto. La segunda abertura es la salida, situada en la pared norte de la celda de la esquina noreste.

Dos celdas que compartan un lado pueden estar conectadas por un paso o separadas por una sección de pared interior delgada de un metro de longitud. Desde cada celda se puede pasar a cualquier celda con la que comparta un lado si no hay una pared entre ambas. Además, se puede atravesar libremente la salida. La entrada permanece abierta solo hasta que el héroe entra en el laberinto. Entonces se cierra inmediatamente y no vuelve a abrirse hasta que el héroe llega a salvo a la salida.

Los caracteres «K3» indican a un caminante experimentado que el laberinto tiene la siguiente estructura. Primero, de todas las secciones posibles de paredes interiores delgadas (hay $n \times (n-1)$ secciones norte-sur y otras tantas este-oeste), se selecciona al azar un tercio, redondeando hacia abajo si no es entero, y se consideran en un orden aleatorio fijo. Después se colocan en el laberinto siguiendo ese orden. Si colocar una sección dividiera el cuadrado que contiene el laberinto en partes desconectadas, se descarta esa sección y no se coloca. Por tanto, se garantiza que el laberinto resultante es conexo.

Malcolm se alegró: sabía tanto del laberinto que sin duda podría llegar a la salida. Su objetivo es partir de la celda del bosque adyacente a la entrada y llegar a la celda del bosque adyacente a la salida. Además, debe darse prisa: quien vaya de la entrada a la salida lo bastante rápido verá el tesoro escondido en el bosque cerca de la salida. Por supuesto, esto solo es cierto si nadie ha llegado antes al tesoro.

Sin embargo, pensándolo mejor, hay motivos para preocuparse. Primero, Malcolm no conoce el tamaño del laberinto: la longitud del lado del cuadrado $n$ puede ser cualquier número entero de metros entre $10$ y $200$. Segundo, el laberinto es tan oscuro como el bosque circundante, así que Malcolm tiene que moverse casi a ciegas. Al principio de cada paso, el héroe elige uno de los cuatro puntos cardinales: norte, este, sur u oeste. Después intenta avanzar un metro en esa dirección. Si choca con un obstáculo, permanece donde estaba. En caso contrario, pasa a la celda vecina en la dirección elegida. El tiempo de cada paso no depende de su resultado, de modo que lo que importa es el número total de pasos.

Ayuda al héroe a moverse de forma que llegue a la celda requerida lo bastante rápido. La solución se considerará correcta si el héroe da como máximo $5 \cdot n + 300$ pasos y llega a la celda situada fuera de la salida del laberinto.

Interacción

En este problema, el programa del jurado reacciona a los comandos que una solución escribe en la salida estándar. Cada comando determina el siguiente paso de Malcolm. Se escribe un comando en cada línea y consta de una letra inglesa mayúscula: «N» para avanzar al norte, «E» al este, «S» al sur y «W» al oeste.

Por cada comando emitido, el programa del jurado responde inmediatamente con una línea enviada a la entrada estándar de la solución que contiene una palabra en letras inglesas minúsculas: «no» si un obstáculo impidió el paso, «ok» si el paso tuvo éxito pero el héroe no llegó a la celda objetivo, y «end» si el paso tuvo éxito y el héroe llegó a la celda objetivo. Tras recibir «end», la solución debe terminar sin producir más salida.

Para evitar el almacenamiento de la salida en un búfer, vacía el búfer de salida después de cada comando. Puedes hacerlo, por ejemplo, con fflush (stdout) en C o C++, System.out.flush () en Java, flush (output) en Pascal o sys.stdout.flush () en Python.

En cada prueba, el laberinto se fija de antemano después de generarse aleatoriamente.

Si una solución ha dado al menos $100\,000$ pasos, pero aún no ha excedido el límite de tiempo ni ha llegado a la celda objetivo, la prueba termina con el resultado «Respuesta incorrecta».

Ejemplos

Nota

La imagen anterior muestra el laberinto generado en la primera prueba. Malcolm empieza en la celda marcada con un círculo y tiene que llegar a la marcada con una cruz. Por ejemplo, este laberinto puede recorrerse usando la siguiente secuencia de comandos (debajo de los comandos aparecen los resultados de su ejecución):

N W N E N W N E N E E E S E E N N N N N E N E S E E N
ok no ok ok ok ok ok ok ok ok ok no ok ok ok ok ok ok ok ok ok ok ok no ok ok end

En la imagen, esta solución se representa mediante una línea gris gruesa.