Random Gap

Pseudo-random number generators (RNGs) are widely used in statistical computing. One of the simplest and most common is the linear congruential generator, which produces the $n$-th number $R_n$ from the previous one:

$R_n = (a \cdot R_{n-1} + c) \bmod m$

where $a$, $c$, and $m$ are fixed constants and $R_0$ is the starting seed. For example, with $a = 15$, $c = 7$, $m = 100$, and $R_0 = 1$ the sequence is $1, 22, 37, 62, 37, 62, \dots$

Such generators are fast and, with well-chosen constants, produce good random sequences. One measure of quality is the longest gap between the values the sequence produces. Consider the set of distinct values that appear in the sequence, and find two of them $R_i < R_j$ such that:

1. no produced value $R_k$ satisfies $R_i < R_k < R_j$ (that is, $R_i$ and $R_j$ are neighbours among the distinct values), and
2. the difference $R_j - R_i$ is as large as possible.

Output that maximal difference. If the sequence produces only one distinct value, output $0$.

The input contains four integers $a$, $c$, $m$, and $R_0$.

Output a single integer: the maximal difference described above.

• $0 \le a, c, R_0 \le 10^7$
• $1 \le m \le 16000000$
• $a \cdot m + c < 2^{32}$