중국인의 나머지 정리

Johnny는 컴퓨터 과학과 학생이다. 이번 학기에 그는 중국인의 나머지 정리를 완벽하게 익혔다. 다음 강의를 기다리던 중 Maggie가 숙제를 풀지 못한다고 불평하는 소리를 들었다. "모듈로"와 "연립방정식"이라는 익숙한 단어가 들리자마자 그는 곤경에 빠진 Maggie에게 도움을 주겠다고 나섰다. 알고 보니 Maggie의 과제는 Johnny가 익숙하게 풀던 것과는 전혀 달랐고, 다음과 같은 형태였다:

$\left\{\begin{array}{ccc} a_1 & \equiv & b_1 \pmod{m} \\ a_2 & \equiv & b_2 \pmod{m} \\ \vdots & \vdots & \vdots \\ a_n & \equiv & b_n \pmod{m} \end{array}\right.$

(여기서 $\equiv$는 모듈로 $m$에 대한 합동을 뜻한다.) 주어진 $a_1, b_1, \dots, a_n, b_n$에 대해 Maggie는 모든 방정식이 성립하도록 하는 가장 큰 $m$을 구해야 한다. Maggie는 이미 방정식들을 처리하기 시작했고, 각 $i$에 대해 $a_i \geq b_i$임을 확인했다. Johnny는 실패해서 체면을 잃을 수 없다. 그를 도와 이 과제를 해결하자.

첫째 줄에 방정식의 개수 $n$ ($1 \leq n \leq 10^5$)이 주어진다.

둘째 줄에 $n$개의 정수 $a_1, a_2, \dots, a_n$이 공백 하나로 구분되어 주어진다. 이는 연속한 방정식들의 좌변에 해당한다.

셋째 줄이자 마지막 줄에 $n$개의 정수 $b_1, b_2, \dots, b_n$이 공백 하나로 구분되어 주어진다. 이는 연속한 방정식들의 우변에 해당한다.

각 $i$ ($1 \leq i \leq n$)에 대해 $0 \leq b_i \leq a_i \leq 10^{18}$이 성립한다. 연립방정식은 자명하지 않다. 즉, 어떤 $i$ ($1 \leq i \leq n$)에 대해 $a_i \neq b_i$이다.

첫째 줄이자 유일한 줄에 하나의 정수를 출력한다. 이는 주어진 연립방정식이 성립하는 가장 큰 $m$이다.

예제 1의 경우 연립방정식 $\left\{\begin{array}{ccc} 7 & \equiv & 3 \pmod{4} \\ 17 & \equiv & 5 \pmod{4} \\ 9 & \equiv & 1 \pmod{4} \end{array}\right.$ 가 성립하며, $m > 4$일 때 성립하지 않음은 쉽게 확인할 수 있다.

예제 2의 경우 연립방정식 $\left\{\begin{array}{ccc} 4 & \equiv & 2 \pmod{1} \\ 6 & \equiv & 2 \pmod{1} \\ 5 & \equiv & 2 \pmod{1} \end{array}\right.$ 가 성립하며, $m > 1$일 때 성립하지 않음은 쉽게 확인할 수 있다.