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 R_{n} as
R_{n} = (aR_{n - 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 R_{0} = 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 R_{0},
find such two elements R_{i} < R_{j} that:

there are no other R_{k}R_{i} ≤ R_{k} ≤ R_{j},

the difference R_{j} − R_{i} is maximal.

Input file format

Input file contains integer numbers acmR_{0}.

Output file format

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

Constraints

0 ≤ a, c, R_{0} ≤ 10^{7},
1 ≤ m ≤ 16000000,
am + c < 2^{32}.