C. Magic Ship

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You a captain of a ship. Initially you are standing in a point (x1,y1)(x1,y1) (obviously, all positions in the sea can be described by cartesian plane) and you want to travel to a point (x2,y2)(x2,y2).

You know the weather forecast — the string ss of length nn, 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 s1s1, the second day — s2s2, the nn-th day — snsn and (n+1)(n+1)-th day — s1s1 again and so on.

Ship coordinates change the following way:

  • if wind blows the direction U, then the ship moves from (x,y)(x,y) to (x,y+1)(x,y+1);
  • if wind blows the direction D, then the ship moves from (x,y)(x,y) to (x,y−1)(x,y−1);
  • if wind blows the direction L, then the ship moves from (x,y)(x,y) to (x−1,y)(x−1,y);
  • if wind blows the direction R, then the ship moves from (x,y)(x,y) to (x+1,y)(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)(x,y) it will move to the point (x−1,y+1)(x−1,y+1), and if it goes the direction U, then it will move to the point (x,y+2)(x,y+2).

You task is to determine the minimal number of days required for the ship to reach the point (x2,y2)(x2,y2).

Input

The first line contains two integers x1,y1x1,y1 (0≤x1,y1≤1090≤x1,y1≤109) — the initial coordinates of the ship.

The second line contains two integers x2,y2x2,y2 (0≤x2,y2≤1090≤x2,y2≤109) — 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 nn (1≤n≤1051≤n≤105) — the length of the string ss.

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

Output

The only line should contain the minimal number of days required for the ship to reach the point (x2,y2)(x2,y2).

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

Examples

input

Copy

0 0
4 6
3
UUU

output

Copy

5

input

Copy

0 3
0 0
3
UDD

output

Copy

3

input

Copy

0 0
0 1
1
L

output

Copy

-1

Note

In the first example the ship should perform the following sequence of moves: "RRRRU". Then its coordinates will change accordingly: (0,0)(0,0) →→ (1,1)(1,1) →→ (2,2)(2,2) →→ (3,3)(3,3) →→ (4,4)(4,4) →→ (4,6)(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)(0,3) →→ (0,3)(0,3) →→ (0,1)(0,1) →→ (0,0)(0,0).

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

题意：

          给出串的起点坐标和要达到的终点坐标，在已知风的方向的情况下，问能否达到终点需要的最少天数。如果不能达到输出“-1”；

注意：

          题目给出的风的方向的天数并不只是题目中的n天，而是以n天为循环节一直往后循环，船可以在风的作用下运动，也可以在自身提供动力运动，风每天都要趋势船运动，而船本身可以可以选择是否运动和方向。当然船自身可以不提供动力而只是随风运动。

思路：

          很明显船在x轴和y轴的运动是相互独立的，可以单独计算。开始想要模拟的，但发现数据n为1e5，而且还不知道要循环多少次，所以放弃了。现在换个角度思考，如果我们知道船运动的我天数，那船是否能到达终点其实就可以判断出来了。可以先处理船在n天里仅依靠风运动的距离保存在up[](y轴方向)和rl[](x轴方向)，起点和终点的距离dx=x2-x1,dy=y2-y1，假设运动了mid天，那在风的影响下的运动距离就是disyy=up[n]*(mid/n)+up[mid%n],disxx=rl[n]*(mid/n)+rl[mid%n],那么船现在距离终点的距离就是dx=abs(disx-disxx),dy=abs(disy-disyy);另一方面，船自身还可以运动mid天，如果（dx+dy）<=mid,那么船可以到达终点，否则不可以，mid>(dx+dy)时，当船已经到达终点后便可以选择不动；

至此，我们便可以二分天数处理这个问题，上限需要开到至少1e15（亲测过1e14不可以）；

代码如下：

#include<bits/stdc++.h>
using namespace std;

#define ll long long
const int MAXN = 2*100 * 1000 + 10;
int x1, y11, x2,y22,n;
int ud[MAXN], rl[MAXN];
string s;

int main() {
	
	scanf("%d%d",&x1,&y11);
	scanf("%d%d",&x2,&y22);
	scanf("%d",&n);
	cin >> s;
	s.insert(s.begin(),'t');				//此处插入只是为了方便下面for循环书写
	ud[0] = rl[0] = 0;
	for (int i = 1; i < s.size(); i++) {
		if (s[i] == 'U')ud[i]=ud[i-1]+1,rl[i]=rl[i-1];
		else if (s[i] == 'D')ud[i]=ud[i-1]-1,rl[i]=rl[i-1];
		else if (s[i] == 'R')rl[i]=rl[i-1]+1,ud[i]=ud[i-1];
		else rl[i]=rl[i-1]-1,ud[i]=ud[i-1];
	}

	ll R = 1e15, L = 0;
	ll disx = (x2 - x1), disy = (y22 - y11);
	while (R > L) {							//二分天数
		ll mid = (R + L) / 2;
		ll cnt = mid / n, res = mid % n;
		ll disxx = cnt * rl[n] + rl[res];
		ll disyy = cnt * ud[n] + ud[res];
		if (abs(disxx - disx) + abs(disyy - disy) <= mid  )R = mid;
		else
			L = mid+1;
	}
	if (R ==1e15)
		puts("-1");
	else
		cout << R << endl;
	return 0;
}