ADAHLIA - Ada and Dahlia

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: Ai+1=(a*Ai+b)%c.

Input

The first and the only line contains five integers (N,a,b,c,A0): 2 ≤ N ≤ 4*107, the number of flowers, and 0 ≤ a, b ≤ 1018, 1 ≤ c ≤ 1018, 0 ≤ A0 < 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

Added by:Morass
Date:2017-12-01
Time limit:4s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Proposed by Mr. Puchýř

hide comments
2017-12-03 17:28:12 Michael Kharitonov
@Blue.Mary, in this problem array generation is harder to implement and it takes almost half the time.
tip: you can use __int128_t/__uint128_t in G++14

Last edit: 2017-12-03 17:32:42
2017-12-02 10:54:22
@Rampage] Blue.Mary: As X-Tazy said, you don't have to sort the array in this problem. Sadly solution from tomatoe works too (sadly, it is even faster due to caching :'( )
2017-12-02 10:10:37
@[Rampage] Blue.Mary, you can solve this one without really sorting the array.
2017-12-02 03:12:09 [Rampage] Blue.Mary
Is there any big difference between this problem and problem http://www.spoj.com/problems/ADATOMAT/?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.