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 N1) 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_{0}): 2 ≤ N ≤ 4*10^{7}, the number of flowers, and 0 ≤ a, b ≤ 10^{18}, 1 ≤ c ≤ 10^{18}, 0 ≤ A_{0} < 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
hide comments
Michael Kharitonov:
20171203 17:28:12
@Blue.Mary, in this problem array generation is harder to implement and it takes almost half the time.


morass:
20171202 10:54:22
@Rampage] Blue.Mary: As XTazy 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 :'( ) 

secta:
20171202 10:10:37
@[Rampage] Blue.Mary, you can solve this one without really sorting the array. 

[Rampage] Blue.Mary:
20171202 03:12:09
Is there any big difference between this problem and problem http://www.spoj.com/problems/ADATOMAT/? 
Added by:  Morass 
Date:  20171201 
Time limit:  4s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Proposed by Mr. Puchýř 