Problem C. Random Gap

Author:A. Klenin   Time limit:8 sec
Input file:input.txt   Memory limit:2 Mb
Output file:output.txt  

Statement

The pseudo-random number genegators (or RNGs for short) are widely used in statistical calculations. One of the simplest and ubiquitious is the linear congruence RNG, that calculates the n-th random number Rn as Rn = (aRn - 1 + c) mod m, where a, c and m are constants. For example, the sequence for a = 15, c = 7, m = 100 and starting value R0 = 1 is 1, 22, 37, 62, 37, 62, ...

Linear RNG is very fast, and can yield surprisinly good sequence of random numbers, given the right choice of constants. There are various measures of RNG quality, and your task is to calculate one of them, namely the longest gap between members of the sequence. More precisely, given the values of a, c, m, and R0, find such two elements Ri < Rj that:

  1. there are no other Rk Ri &le; Rk &le; Rj,
  2. the difference Rj &minus; Ri is maximal.

Input file format

Input file contains integer numbers a c m R0.

Output file format

Output file should contain the single number — the maximal difference found.

Constraints

0 &le; a, c, R0 &le; 107, 1 &le; m &le; 16000000, am + c < 232.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
15 7 100 1
25
2
2 0 127 5
26

0.078s 0.010s 13