In an infinite two-dimensional surface, you are chasing a robot that moves in a certain way. Given the initial position of you and the robot and the robot's motion, find the minimum time required for you to catch up with it. If you can't catch up, output -1.

The motion mode of the robot begins with a line length of N. The string of N is given. The string contains only four uppercase letters: 'U', 'D', 'L', and 'R'. Represents the robot to move up, down, left, and right one unit respectively. In addition, it takes a minute for the robot to move each unit distance, and the sequence of movements is repeated over and over again.

For you, you can choose to move one unit per minute in either up, down, left, or right direction. You can also choose not to move.

Input

The input data consists of three rows:

The first line contains four integers: Xr, Yr, Xp, Yp represent the horizontal and vertical coordinates of the initial position of the robot and the horizontal and vertical coordinates of your position, respectively.

The second row is a positive integer N: The length of the string that represents the movement of the robot.

The third line contains N characters represent the way the robot moves.

Output the minimum time it takes you to catch up with the robot. If not, output 1.

please use the binary search and JAVA to do this question!!

Sample Input 5 7 1 1 4 DDDD Sample Output 5