무작위 간격

의사난수 생성기(RNG)는 통계 계산에서 널리 쓰인다. 그중 가장 단순하고 흔한 것이 선형 합동 생성기로, 바로 앞 값으로부터 $n$번째 수 $R_n$을 다음과 같이 만든다.

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

여기서 $a$, $c$, $m$은 고정된 상수이고 $R_0$은 시작 씨앗값이다. 예를 들어 $a = 15$, $c = 7$, $m = 100$, $R_0 = 1$이면 수열은 $1, 22, 37, 62, 37, 62, \dots$ 이다.

이런 생성기는 빠르고, 상수를 잘 고르면 좋은 난수열을 만든다. 품질을 재는 한 가지 척도는 수열이 만들어 내는 값들 사이의 가장 큰 간격이다. 수열에 등장하는 서로 다른 값들의 집합을 생각하고, 그중 다음 두 조건을 만족하는 값 $R_i < R_j$를 찾아라.

1. $R_i < R_k < R_j$인 값 $R_k$가 수열에 존재하지 않는다(즉 $R_i$와 $R_j$는 서로 다른 값들 중에서 이웃한다).
2. 차이 $R_j - R_i$가 최대이다.

이 최대 차이를 출력하라. 수열이 만들어 내는 서로 다른 값이 하나뿐이면 $0$을 출력한다.

네 정수 $a$, $c$, $m$, $R_0$이 주어진다.

위에서 설명한 최대 차이를 정수 하나로 출력한다.

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