문제 172
중국인의 나머지 정리
길이가 $N$인 정수 수열 $A_1, A_2, \cdots, A_N$과 양의 정수 수열 $M_1, M_2, \cdots, M_N$이 주어진다.
다음 조건을 모두 만족하는 음이 아닌 정수 $X$ 중 최솟값을 구해 보자.
\[
X \equiv A_i \pmod{M_i} \qquad (1 \le i \le N).
\]
조건을 만족하는 $X$가 존재하지 않을 수도 있다.
입력
첫 번째 줄에 정수 $N$이 주어진다. $(1 \le N \le 200\,000)$
두 번째 줄부터 $N$개의 줄에 걸쳐 $i=1, 2, \cdots, N$의 순서로 두 정수 $A_i$, $M_i$가 공백으로 구분되어 주어진다. $(-10^{18} \le A_i \le 10^{18}; 1 \le M_i \le 10^9; \operatorname{lcm}(M_1, M_2, \cdots, M_N) \le 10^{18})$
출력
조건을 만족하는 $X$가 존재한다면 $X$의 최솟값과 $M_1, M_2, \cdots, M_N$의 최소공배수를 공백으로 구분하여 출력한다.
그렇지 않다면 $-1$을 출력한다.
예제 입력 1
2 2 6 5 9
예제 출력 1
14 18
예제 입력 2
2 1 2 0 4
예제 출력 2
-1
예제 입력 3
1 -1 7
예제 출력 3
6 7