Опасные игры

시간 제한1초메모리 제한1024 MB

요약

n x n 격자에 숨겨진 폭탄의 방향만 알려 주는 장치를 사용해 폭탄의 위치를 찾아 보고한다.

난이도: 보통10점 중 5점
유형: 이분 탐색, 구간, 구현
정답자: 아직 제출이 없습니다

문제

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

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

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

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

예제2

예제 1
입력
```
3

NW

OK
```
예상 출력
```
2 2

1 1
```
예제 2
입력
```
5

SE

SW

W

OK
```
예상 출력
```
2 2

3 5

4 4

4 3
```