你是一艘船的船长。最初,你站在一个点 $$$(x_1, y_1)$$$(显然,海中的所有位置都可以用笛卡尔平面来描述),并且你想要前往一个点 $$$(x_2, y_2)$$$。
你知道天气预报——长度为$$$n$$$的字符串$$$s$$$,仅由字母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”。
示例
输入 #1
0 0 4 6 3 UUU
输出 #1
5
输入 #2
0 3 0 0 3 UDD
输出 #2
3
输入 #3
0 0 0 1 1 L
输出 #3
-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)$$$ 点。