В этой интерактивной задаче вам нужно добраться от входа в неизвестный лабиринт до его выхода, затратив не слишком много времени.

Знаменитый воин Malcolm, герой Arcania, шёл ночью через тёмный лес. Он шёл уже долго и начал думать, что заблудился, но вдруг наткнулся на каменную стену на своём пути. Знаки на каменной плите, видневшиеся под опавшими листьями, ясно указывали, что он обнаружил лабиринт, построенный гномами.

Герой мало знает о лесе и растущих в нём деревьях. Зато он провёл много времени в компании гномов, поэтому теперь может многое узнать о лабиринте, лишь взглянув на его обозначения.

Обозначения на этом лабиринте образуют символы «SK3». Символ «S» означает, что лабиринт квадратный, то есть его пол состоит из $n \times n$ квадратных клеток размером $1 \times 1$ метр каждая. Вокруг этих клеток проходит тонкая сплошная стена с двумя проёмами. Первый — это вход, рядом с которым стоит герой. Он находится в южной стене юго-западной угловой клетки лабиринта. Второй проём — выход в северной стене северо-восточной угловой клетки.

Любые две клетки, имеющие общую сторону, могут быть соединены проходом или разделены метровым отрезком тонкой внутренней стены. Из каждой клетки можно перейти в любую соседнюю по стороне клетку, если между ними нет стены. Кроме того, через выход можно проходить свободно. Вход открыт лишь до того момента, когда герой войдёт в лабиринт. После этого он немедленно закрывается и снова открывается только тогда, когда герой благополучно доберётся до выхода.

Символы «K3» сообщают опытному путешественнику, что лабиринт имеет следующую структуру. Сначала из всех возможных отрезков тонких внутренних стен (всего имеется $n \times (n-1)$ отрезков направления север–юг и столько же направления восток–запад) случайно выбирается одна треть, с округлением вниз, если число не целое, и рассматривается в фиксированном случайном порядке. Затем отрезки помещаются в лабиринт в этом порядке. Если размещение какого-либо отрезка разделило бы квадрат, содержащий лабиринт, на несвязные части, этот отрезок отбрасывается и не размещается. Таким образом, получившийся лабиринт гарантированно связен.

Malcolm обрадовался: он знает о лабиринте так много, что наверняка сможет добраться до выхода. Его цель — начать в клетке леса, соседней со входом, и прийти в клетку леса, соседнюю с выходом. Кроме того, стоит поторопиться: тот, кто достаточно быстро пройдёт от входа до выхода, увидит сокровище, спрятанное в лесу неподалёку от выхода. Конечно, это верно лишь в том случае, если никто не добрался до сокровища раньше.

Но, поразмыслив, можно найти и повод для беспокойства. Во-первых, Malcolm не знает размера лабиринта: длина стороны квадрата $n$ может быть любым целым числом метров от $10$ до $200$. Во-вторых, лабиринт так же тёмен, как окружающий лес, поэтому Malcolm придётся двигаться почти вслепую. В начале каждого шага герой выбирает одно из четырёх основных направлений: север, восток, юг или запад. Затем он пытается переместиться на один метр в этом направлении. Если герой натыкается на препятствие, то остаётся на месте. В противном случае он переходит в соседнюю клетку в выбранном направлении. Время каждого шага не зависит от его результата, поэтому важным является общее количество шагов.

Помогите герою двигаться так, чтобы он достаточно быстро пришёл в нужную клетку. Решение будет считаться правильным, если герой сделает не более $5 \cdot n + 300$ шагов и окажется в клетке снаружи выхода из лабиринта.

Протокол взаимодействия

В этой задаче программа жюри реагирует на команды, которые решение выводит в стандартный поток вывода. Каждая команда определяет следующий шаг Malcolm. Команда записывается в отдельной строке и состоит из одной заглавной английской буквы: «N» — шаг на север, «E» — на восток, «S» — на юг и «W» — на запад.

На каждую команду программа жюри немедленно отвечает строкой, поступающей в стандартный ввод решения. Она содержит одно слово из строчных английских букв: «no», если проход был перекрыт препятствием; «ok», если шаг удался, но герой не попал в целевую клетку; и «end», если шаг удался и герой оказался в целевой клетке. После получения ответа «end» решение должно завершиться, не выводя больше ничего.

Чтобы избежать буферизации вывода, после каждой команды очищайте выходной буфер. Для этого можно использовать, например, fflush (stdout) в C или C++, System.out.flush () в Java, flush (output) в Pascal или sys.stdout.flush () в Python.

В каждом тесте лабиринт заранее фиксируется после случайной генерации.

Если решение сделало хотя бы $100\,000$ шагов, но ещё не превысило ограничение времени и не достигло целевой клетки, тестирование прекращается с результатом «Неправильный ответ».

Примеры

Примечание

На рисунке выше показан лабиринт, сгенерированный в первом тесте. Malcolm начинает в клетке, отмеченной кружком, и должен попасть в клетку, отмеченную крестиком. Например, этот лабиринт можно пройти с помощью следующей последовательности команд (под командами приведены результаты их выполнения):

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

На рисунке это решение показано толстой серой линией.