Magic Ship
Contest: Educational Codeforces Round 60 (Rated for Div. 2)
Difficulty rating: 1900
Tags: binary search

You a captain of a ship. Initially you are standing in a point $$$(x_1, y_1)$$$ (obviously, all positions in the sea can be described by cartesian plane) and you want to travel to a point $$$(x_2, y_2)$$$.

You know the weather forecast — the string $$$s$$$ of length $$$n$$$, consisting only of letters U, D, L and R. The letter corresponds to a direction of wind. Moreover, the forecast is periodic, e.g. the first day wind blows to the side $$$s_1$$$, the second day — $$$s_2$$$, the $$$n$$$-th day — $$$s_n$$$ and $$$(n+1)$$$-th day — $$$s_1$$$ again and so on.

Ship coordinates change the following way:

- if wind blows the direction U, then the ship moves from $$$(x, y)$$$ to $$$(x, y + 1)$$$;
- if wind blows the direction D, then the ship moves from $$$(x, y)$$$ to $$$(x, y - 1)$$$;
- if wind blows the direction L, then the ship moves from $$$(x, y)$$$ to $$$(x - 1, y)$$$;
- if wind blows the direction R, then the ship moves from $$$(x, y)$$$ to $$$(x + 1, y)$$$.

The ship can also either go one of the four directions or stay in place each day. If it goes then it's exactly 1 unit of distance. Transpositions of the ship and the wind add up. If the ship stays in place, then only the direction of wind counts. For example, if wind blows the direction U and the ship moves the direction L, then from point $$$(x, y)$$$ it will move to the point $$$(x - 1, y + 1)$$$, and if it goes the direction U, then it will move to the point $$$(x, y + 2)$$$.

You task is to determine the minimal number of days required for the ship to reach the point $$$(x_2, y_2)$$$.

Input format:
The first line contains two integers $$$x_1, y_1$$$ ($$$0 \le x_1, y_1 \le 10^9$$$) — the initial coordinates of the ship.

The second line contains two integers $$$x_2, y_2$$$ ($$$0 \le x_2, y_2 \le 10^9$$$) — the coordinates of the destination point.

It is guaranteed that the initial coordinates and destination point coordinates are different.

The third line contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of the string $$$s$$$.

The fourth line contains the string $$$s$$$ itself, consisting only of letters U, D, L and R.

Output format:
The only line should contain the minimal number of days required for the ship to reach the point $$$(x_2, y_2)$$$.

If it's impossible then print "-1".

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example the ship should perform the following sequence of moves: "RRRRU". Then its coordinates will change accordingly: $$$(0, 0)$$$ $$$\rightarrow$$$ $$$(1, 1)$$$ $$$\rightarrow$$$ $$$(2, 2)$$$ $$$\rightarrow$$$ $$$(3, 3)$$$ $$$\rightarrow$$$ $$$(4, 4)$$$ $$$\rightarrow$$$ $$$(4, 6)$$$.

In the second example the ship should perform the following sequence of moves: "DD" (the third day it should stay in place). Then its coordinates will change accordingly: $$$(0, 3)$$$ $$$\rightarrow$$$ $$$(0, 3)$$$ $$$\rightarrow$$$ $$$(0, 1)$$$ $$$\rightarrow$$$ $$$(0, 0)$$$.

In the third example the ship can never reach the point $$$(0, 1)$$$.

Example input:
0 0
4 6
3
UUU

Example output:
5

Example input:
0 3
0 0
3
UDD

Example output:
3

Editorial:
Note, that if we can reach the destination in $$$x$$$ days, so we can reach it in $$$y \ge x$$$ days, since we can stay in the destination point by moving to the opposite to the wind direction. So, we can binary search the answer.
To check the possibility to reach the destination point $$$(x_2, y_2)$$$ in $$$k$$$ days we should at first look at the position $$$(x_3, y_3)$$$ the wind moves ship to. Now we can calculate where we can go: since each day we can move in one of four directions or not move at all, we can reach any point $$$(x, y)$$$ with Manhattan distance $$$|x - x_3| + |y - y_3| \le k$$$. So we need to check that $$$|x_2 - x_3| + |y_2 - y_3| \le k$$$.
To calculate $$$(x_3, y_3)$$$ we can note, that there were $$$\lfloor \frac{k}{n} \rfloor$$$ full cycles and $$$k \bmod n$$$ extra days. So it can be calculated with $$$O(1)$$$ time using prefix sums.
Finally, about borders of binary search: to reach the destination point we need to move closer at least by one (it terms of Manhattan distance) from the full cycle of the wind. So, if answer exists then it doesn't exceed $$$(|x_1 - x_2| + |y_1 - y_2|) \cdot n \le 2\cdot 10^{14}$$$.