C. Волшебный корабль
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы являетесь капитаном корабля. Изначально вы стоите в точке $$$(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_1, y_1$$$ ($$$0 \le x_1, y_1 \le 10^9$$$) — первоначальные координаты корабля.

Вторая строка содержит два целых числа $$$x_2, y_2$$$ ($$$0 \le x_2, y_2 \le 10^9$$$) — координаты места назначения.

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

Третья строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — длину строки $$$s$$$.

Четвертая строка содержит саму строку $$$s$$$, состоящую только из букв U, D, L и R.

Выходные данные

В единственной строке выведите минимальное количество дней, необходимое кораблю, чтобы попасть в точку $$$(x_2, y_2)$$$.

Если это невозможно, выведите «-1».

Примеры
Входные данные
0 0
4 6
3
UUU
Выходные данные
5
Входные данные
0 3
0 0
3
UDD
Выходные данные
3
Входные данные
0 0
0 1
1
L
Выходные данные
-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)$$$.