Ищем клад — 1

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

Известны координаты клада и указания, которым нужно следовать, чтобы его найти. Каждое указание карты состоит из одного слова и, возможно, одного натурального числа. Слово — одно из набора: «вперёд», «налево», «направо», «разворот» или «стоп».

После слова «вперёд» следует количество шагов, которое следует пройти в том направлении, куда мы в данный момент смотрим. Слова «налево» или «направо» означают, что нужно изменить направление взгляда под прямым углом, «разворот» — что прямо на обратное. Команда «стоп» означает остановку.

Найдите минимальное количество указаний карты, которое нужно выполнить, чтобы прийти к кладу.

Формат ввода

Сначала вводятся два числа на отдельных строчках: координаты клада по оси икс (запад-восток) и игрек (юг-север).

Затем следует некоторое количество указаний карты. Каждое указание карты состоит из одного слова и, возможно, одного натурального числа на отдельной строке. Слово — одно из набора: «вперёд», «налево», «направо», «разворот» или «стоп».

Формат вывода

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

Пример1

Ввод

-2

9

вперёд

9

налево

вперёд

2

разворот

вперёд

17

стоп

Вывод

3

запад

Пример2

Ввод

0

1

вперёд

2

разворот

вперёд

1

Вывод

3

юг