该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在二维的平面上，小明驾驶着一架飞船，起点为$\red{(x1,y1)，}$终点为$\red{(x2,y2)}$

小明知道了接下来的天气预报，每天都会吹上、下、左、右中一个方向的风。天气预报可以用一个字符 串$\red{s}$表示，包含$\red{U,D,L,R}$四种字母，表示吹上、下、左、右中一个方向的风。其中第一天的风向为$\red{s_1}$ ，第二天吹的风向为$\red{s_2,...}$第$\red{n}$天吹的风向为$\red{s_n，}$第$\red{n+1}$天吹的风向为$\red{s_1...}$以此类推。

假如吹的风往上, 船会从$\red{(x,y)}$移动到$\red{(x,y+1)}$;

假如吹的风往下,船会从$\red{(x,y)}$移动到$\red{(x,y-1)}$;

假如吹的风往左, 船会从$\red{(x,y)}$移动到$\red{(x-1,y)}$;

假如吹的风往右, 船会从$\red{(x,y)}$移动到$\red{(x+1,y)}$;

同时小明每天也可以从上下左右中选择一个方向，移动一个单位，即每天的位移为风向和小明自己移动 的叠加。例如某天风向向上，小明往左移动了一个单位，那么小明会从$\red{(x,y)}$移动到$\red{(x-1,y+1)}$

你现在需要帮助小明，计算出最少需要多少天可以到达终点。

输入格式

第一行两个整数表示$\red{x1,y1}$。

第二行两个整数表示$\red{x2,y2}$。

第三行一个整数 ,表示$\red{s}$的长度。

第四行，字符串$\red{s}$

输出格式

输出最少可以到达目的地的天数，如果到达不了输出$\red{-1}$

样例

输入样例

0 0
4 6
3
UUU

输出样例

5

提示

对于$\red{50\%}$的数据，$\red{1<=n<=1000,0<=x1,y1,x2,y2<=1000}$。

对于$\red{100\%}$的数据，$\red{1<=n<=10^5,0<=x1,y1,x2,y2<=10^9}$。