28600번 - Опасные игры 다국어인터랙티브

Это интерактивная задача.

Однажды утром Вай получила посылку от Джинкс, где обнаружила радиопередатчик и схематический рисунок бомбы с подписью <<НАЙДИ МЕНЯ>>. Передатчик, как оказалось, указывает направление до бомбы, но может сделать это ограниченное число раз, о чем многозначительно говорит все уменьшающаяся красная цифра на экране.

Вай знает, что бомба спрятана где-то в городе на участке размером $n \times n$. Она может встать в любую клетку участка и активировать передатчик, который сообщит, где относительно неё находится взрывчатка. Клетки задаются координатами, первая координата --- номер строки сверху-вниз, вторая --- номер столбца слева-направо. Если Вай уже в клетке с бомбой, то передатчик выдаст <<OK>>, и бомба будет деактивирована, иначе выдаст направление, в котором находится бомба относительно текущей позиции Вай.

Направление может принимать одно из значений <<N>>, <<S>>, <<W>>, <<E>>, <<NW>>, <<NE>>, <<SW>> или <<SE>>. 'N' означает вверх, 'S' --- вниз, 'W' --- влево, 'E' --- вправо, а их комбинация, соответственно, --- комбинацию из двух направлений. К примеру, если ответ будет <<NE>>, то это значит, что клетка с бомбой находится сверху справа от текущей.

В первой строке интерактор сообщает вашей программе целое число $n$ --- длину стороны поля, на котором ведется поиск ($1 \leqslant n \leqslant 10^9$).

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

Ваша программа должна передавать интерактору запросы в формате <<x y>> (без кавычек), где $x$ и $y$ --- координаты интересующей вас клетки по вертикали и горизонтали, соответственно ($1 \leqslant x, y, \leqslant n$). Каждый запрос должен быть выведен на отдельной строке и должен заканчиваться сбросом буфера потока вывода (cout.flush() в C++, System.out.flush() в Java, sys.stdout.flush() в Python).

В ответ на запрос $(x, y)$ интерактор сообщит относительное положение искомой клетки поля на отдельной строке. Если искомая клетка не совпадает с $(x, y)$, ответ интерактора будет являться конкатенацией двух частей, первая из которых может быть равна 'N', 'S' или пустой строке, а вторая --- 'W', 'E' или пустой строке. Каждый символ отвечает за положение искомой клетки относительно $(x, y)$. Символ 'N' означает, что искомая клетка находится выше, 'S' --- ниже, 'W' --- левее, 'E' --- правее.

Если запросом $(x, y)$ ваша программа угадывает искомую клетку, интерактор отвечает в новой строке словом <<OK>> (без кавычек) и завершается. Считав такой ответ, ваша программа тоже должна завершиться, иначе может быть получен вердикт TL или IL.

Всего ваша программа может сделать не более $50$ запросов к интерактору. Как только ваша программа превышает это ограничение, интерактор завершается с ошибкой WA. Если ваша программа при этом не завершается, может быть получен вердикт TL или IL.