Magic Ship

题意翻译

## 题目描述 坐标系上有一只小船，现在想从 $(x_1,y_1)$ 去 $(x_2,y_2)$ 。每时刻都有风，会把船往对应的风向吹一个单位（比如北风会把船往南吹），风是循环的，吹完 $s_1 \sim s_n$ 就又会从 $s_1$ 开始。船在每一时刻都可以向指定方向移动一个单位。求船到目的地的最少时间，如果不能到达输出 **-1** 。 ## 输入格式 第一行为 $x_1,y_1$， 第二行为 $x_2,y_2$， 第三行为正整数 $n$， 第四行为风的方向，`U/D/L/R`表示风把船往`上/下/左/右`吹。 ## 输出格式 共一行，表示最少时间。不能到达输出 **-1** 。

题目描述

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

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #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

说明

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