As you might already know, Ada the Ladybug is a farmer. Beside fruit and vegetable, Ada grows flowers. At the moment she plans to go to a competition with her dahlias. The evaluation of bunch of dahlias is simple: Jury sorts all dahlias by the diameters of blooms and takes the maximal difference between any two adjacent dahlias. This will be the score.

The problems is that Ada's flowers are not in sorted order and she wants to know what score she would get if the passes all flowers to jury. To make job easier for you (or at least Ada hopes so), she created a formula which will give you the diameters of blooms (0 to N-1) in actual order: A_i+1=(a*A_i+b)%c.

Input

The first and the only line contains five integers (N,a,b,c,A₀): 2 ≤ N ≤ 4*10⁷, the number of flowers, and 0 ≤ a, b ≤ 10¹⁸, 1 ≤ c ≤ 10¹⁸, 0 ≤ A₀ < c

Output

Output the maximum difference of elements (if they would be sorted).

Example Input

10 2 3 31 7

Example Output

8

Example Input

4 4 6 11 6

Example Output

2

Example Input

50 3 11 41 0

Example Output

8

Example Input

1000 666 777 1234567 11

Example Output

10817

Example Input

10000000 612 521 124578541254695 666666

Example Output

230017823