题目背景

There once was a ship that put to sea

The name of the ship was the Billy of Tea

The winds blew up, her bow dipped down

O blow, my bully boys, blow (huh)

Soon may the Wellerman come

To bring us sugar and tea and rum

One day, when the tonguin' is done

We'll take our leave and go

She had not been two weeks from shore

When down on her, a right whale bore

The captain called all hands and swore

He'd take that whale in tow (huh)

Soon may the Wellerman come

To bring us sugar and tea and rum

One day, when the tonguin' is done

We'll take our leave and go

题目描述

波奇酱是一位船长。起初他站在点 $(x_1,y_1)$ 上(显然，海中的所有位置都可以用笛卡尔平面来描述)，他想前往点 $(x_2,y_2)$ 。

他知道天气预报--长度为 $n$ 的字符串 $s$ ，仅由字母 U、D、L 和 R 组成。此外，天气预报是周期性的，例如，第一天风向为$s_1$,第二天为$s_2$,第$n$天为$s_n$，以此类推。

船只坐标的变化方式如下：

• 如果风向为 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)$ 点。

你的任务是帮助波奇酱确定该船到达点 $(x2, y 2)$ 所需的最少天数。

输入格式

第一行包含两个整数$x_1,y_1( 0≤x_1,y_1≤10^9 )$

第一行包含两个整数$x_2,y_2( 0≤x_2,y_2≤10^9 )$

可以保证初始坐标和目的点坐标是不同的。

第三行包含一个整数$n( 1≤n≤10^5 )$ - 字符串$s$的长度。

第四行包含字符串 $s$ 本身，仅由字母 U、D、L 和 R 组成。

输出格式

唯一一行应包含船到达点 $(x_2,y_2)$ 所需的最少天数。 如果不可能，则打印"-1"。

输入输出样例 #1

输入 #1

0 0
4 6
3
UUU

输出 #1

5

输入输出样例 #2

输入 #2

0 3
0 0
3
UDD

输出 #2

3

输入输出样例 #3

输入 #3

0 0
0 1
1
L

输出 #3

-1

说明/提示

在第一个示例中，船只应执行以下一系列动作："RRRRU"。然后它的坐标也会相应改变： (0,0) → (1,1) → (2,2) → (3,3) → (4,4) → (4,6)

在第二个示例中，船只应该执行以下的移动顺序："DD"(第三天它应该停留在原地)。然后，它的坐标将发生相应的变化： (0,3) → (0,3) → (0,1) → (0,0)

在第三个例子中，船只永远无法到达 (0,1) 点。