Рабочее место участника

Конфетный город разделен перпендикулярными улицами на квадратные кварталы. На каждом перекрестке стоит банановый стражник. Финн хочет встретиться с Принцессой и расспрашивает стражников на перекрестках о её местонахождении. Стражники знают о местоположении Принцессы, но путаются с направлениями, поэтому могут показать на дорогу, ведущую в прямо противоположном направлении. Формально, если `|X_i\ -\ X_P|\ >\ |Y_i\ -\ Y_P|`, где `(X_i,\ Y_i)` – координаты стражника, `(X_P,\ Y_P)` – координаты Принцессы, то стражник может с равной вероятностью показать направление W (запад) или E (восток). Если `|X_i\ -\ "XP"|\ <\ |Y_i\ -\ Y_P|`, то стражник может показать направление N (север) или S (юг). Если `|X_i\ -\ X_P|\ =\ |Y_i\ -\ Y_P|`, то стражник может показать любое из четырех направлений. Стражники не меняют своих указаний.

Гарантируется, что в начальный момент `1\ ≤\ |X_F\ -\ X_P|\ +\ |Y_F\ -\ Y_P|\ ≤\ 300`, где `(X_F,\ Y_F)` – координаты Финна. Напишите программу, которая поможет Финну найти Принцессу, пройдя не более 2000 перекрестков.

При старте программа получает строку, содержащую первое указание от стражника на местоположение принцессы. Программа должна вывести строку, содержащую один символ N, S, W или E — в каком направлении нужно идти дальше. После вывода программа должна сделать принудительную запись буфера вывода (в C++ это делает endl, в C нужно использовать fflush(stdout), в Pascal – flush(output)). После вывода программа получает указания от стражника на очередном перекрестке или сообщение "PRINCESS!", если Принцесса была обнаружена на этом перекрестке. При появлении такого сообщения программа должна завершить работу. Если программа не найдет Принцессу за 2000 перемещений, то программа получает вердикт WA "Неверный ответ".

N
S
PRINCESS!

S
S