\(x \equiv a_1 \pmod{n_1}\)이고 \(x \equiv a_2 \pmod{n_2}\)를 만족하는 가장 작은 음이 아닌 정수 \(x\)를 구하시오. 여기서 \(n_1\)과 \(n_2\)는 서로소이며, 그러한 \(x\)는 \([0, n_1\ n_2)\)에 유일하게 존재한다.

한 줄에 네 정수 \(a_1\), \(n_1\), \(a_2\), \(n_2\)가 주어진다 (\(0 \le a_1 < n_1\), \(0 \le a_2 < n_2\), \(1 \le n_1, n_2 \le 10^{9}\), \(\gcd(n_1, n_2) = 1\)).

가장 작은 음이 아닌 해 \(x\)를 출력한다.

riseoj 작성

출처 RiseOJ Basics