Вы являетесь капитаном корабля. Изначально вы стоите в точке \((x_1, y_1)\) (очевидно, позиции в море легко описываются декартовой системой координат) и хотите попасть в точку \((x_2, y_2)\).
Вы знаете прогноз погоды — строку \(s\) длины \(n\), состоящую только из букв U, D, L и R. Буква соответствует направлению ветра. При этом прогноз является циклическим, т.е. в первый день ветер дует в сторону \(s_1\), во второй — в \(s_2\), в \(n\)-й — в \(s_n\), а в \((n+1)\)-й — снова в \(s_1\) и т.д.
Координаты корабля изменяются следующим образом:
- если ветер дует в сторону U, то из точки \((x, y)\) корабль перемещается в точку \((x, y + 1)\);
- если ветер дует в сторону D, то из точки \((x, y)\) корабль перемещается в точку \((x, y - 1)\);
- если ветер дует в сторону L, то из точки \((x, y)\) корабль перемещается в точку \((x - 1, y)\);
- если ветер дует в сторону R, то из точки \((x, y)\) корабль перемещается в точку \((x + 1, y)\).
Также корабль каждый день может плыть в одном из четырех направлений или стоять на месте. Если он плывет, то ровно на 1 единицу. Перемещения корабля и ветра складываются. Если корабль стоит на месте, то считается только направление ветра. Например, если ветер дует в сторону U, и корабль плывет в сторону L, то из точки \((x, y)\) он попадет в точку \((x - 1, y + 1)\), а если будет плыть в сторону U, то попадет в точку \((x, y + 2)\).
Вам нужно определить минимальное количество дней, которое потребуется кораблю, чтобы попасть в точку \((x_2, y_2)\).
Выходные данные
В единственной строке выведите минимальное количество дней, необходимое кораблю, чтобы попасть в точку \((x_2, y_2)\).
Если это невозможно, выведите «-1».
Примечание
В первом тестовом примере кораблю нужно выполнить следующую последовательность действий: «RRRRU», тогда его координаты будут меняться следующим образом: \((0, 0)\) \(\rightarrow\) \((1, 1)\) \(\rightarrow\) \((2, 2)\) \(\rightarrow\) \((3, 3)\) \(\rightarrow\) \((4, 4)\) \(\rightarrow\) \((4, 6)\).
Во втором тестовом примере кораблю нужно выполнить следующую последовательность действий: «DD» (третьим действием нужно стоять на месте), тогда его координаты будут меняться следуюущим образом: \((0, 3)\) \(\rightarrow\) \((0, 3)\) \(\rightarrow\) \((0, 1)\) \(\rightarrow\) \((0, 0)\).
В третьем тестовом примере корабль никак не сможет попасть в точку \((0, 1)\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
0 0
4 6
3
UUU
|
5
|
|
2
|
0 3
0 0
3
UDD
|
3
|
|
3
|
0 0
0 1
1
L
|
-1
|