Задача E. Кот-проводник

Автор:М. Спорышев
Входной файл: input.txt   Ограничение времени:1 сек
Выходной файл: output.txt   Ограничение памяти:256 Мб
Максимальный балл:100  

Условие

Путешествуя по зазеркалью, Алиса набрела на поле, разделенное дорожками на N × M клеток. Дорожки также проходят вокруг границ поля. Назовем узлом точку пересечения двух дорожек. Рядом с Алисой в воздухе висит Чеширский Кот, который говорит ей, в какую сторону идти. Алиса передвигается по дорожке от одного узла к другому в направлении, указанном котом, останавливается и ждет следующего указания.

Если при выполнении очередной команды требуется выйти за границу поля, то вместо ее выполнения Алиса стоит на месте, ожидая следующей команды.

Через некоторое время кот растаял в воздухе, оставив растерянную Алису в каком-то узле поля. Алиса просит сообщить, сколько раз ей нужно перейти от узла к узлу, чтобы как можно быстрее дойти до выхода.

Узлы поля нумеруются от 0 до N по горизонтали слева направо, и от 0 до M по вертикали снизу вверх, то есть нижний левый узел имеет координаты (0, 0). Исходная позиция девочки —– узел с координатами (0, 0), а выход находится в узле с координатами (N, M).

Формат входного файла

В первой строке входного файла содержатся целые числа N M. Во второй строке входного файла содержится список команд кота для Алисы, состоящий из букв l, r, u, d, где u —– вверх, d —– вниз, l —– влево, r —– вправо.

Формат выходного файла

В выходном файле должно содержаться одно число —– минимальное количество переходов, которое нужно пройти от текущей позиции Алисы до выхода.

Ограничения

1 ≤ N, M ≤ 1000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
4 3
rru
4
2
3 3
ururuu
1

0.022s 0.006s 9