Welcome to ZOJ
Select Problem
ZOJ Problem Set - 2657

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Two crickets gets know with each other on freecity bbs. They feel very happy chatting with each other, so they want to meet the other. Fortunately, they find they both live the lakeside of QiZhen Lake, which is a circle. Because they can't swim, so they only can move along the lakeside. Then, they set out, unfortunately, they forget to fix a place to meet each other. but they are optimistic, they think that if they jump all the while, they can come up against each other.(The meaning of meeting with each other is that they get to the same place at same time).

You are asked to help the two crickets. Telling them whether they can meet each other.

We can select a point on the circle as the origin, and the clockwise as the positive direction to make a coordinate axis.

You are given five integer X, Y, M, N, L. X is the start coordinate of the first cricket, Y is the other's. The first cricket can jump M once, and the other can jump N. The sign of M,N denote the direction they jump, They use the same time in one jump. L denote the length of the circle lake.


Each line contain five integers, X, Y, M, N, L which satisfy these conditions: 2 <= L <= 1,000,000,000; 0 <= x, y < L;
x != y; 0< |m|,|n|< L


For each case in input, output a number in a line, which denote the minimum steps they can meet. If they can never meet with each other, print "Pat" in this line.

Sample Input:
1 2 3 4 5
10 1 2 2 20
Sample Output:

Author: JIANG Dongming
Source: ZOJ Monthly, February 2006
Submit    Status