CF1117C.Magic Ship

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)$.

你是一艘船的船长。初始时，你位于点 $(x_1, y_1)$（显然，海面上所有位置均可由笛卡尔平面描述），而你的目标是抵达点 $(x_2, y_2)$。

你已知天气预报——一个长度为 $n$ 的字符串 $s$，仅由字母 U、D、L 和 R 组成。每个字母表示风向。此外，该预报具有周期性：第 1 天风向为 $s_1$，第 2 天为 $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)$ 所需的最少天数。

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.

第一行包含两个整数 $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 组成。

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".

唯一的一行应包含飞船到达点 $(x_2, y_2)$ 所需的最少天数。

如果无法到达，则输出 "-1"。

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)$.

在第一个例子中，飞船应执行以下移动序列：“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)$。