23604번 - Chinese Remainder Theorem 다국어

문제

Johnny is a computer science student. This semester he became well versed with the Chinese Remainder Theorem. While waiting for a next lecture he heard that Maggie complained that she cannot solve her homework; as he heard the familiar words "modulo" and "system of equations" he immediately offered his help to the damsel in distress. It turns out that Maggie's task is much different than those that Johnny is accustomed to solve, it is of the following form:

$$ \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. $$

(where $\equiv$ means equivalence modulo) and for the given $a_1, b_1,\ldots, a_n, b_n$ Maggie should compute the largest $m$ such that all of the equations hold. Maggie already started processing the equations and she ensured that $a_i \geq b_i$ for each $i$. Johhny cannot fail and lose his face -- help him to solve the task.

입력

The first line of the input contains a single integer $n$ (1ドル \leq n \leq 10^5$), denoting the number of equations.

The second line contains $n$ integers $a_1 , a_2 , \dots , a_n,ドル each separated by a single space, these are the numbers on the left-hand sides of consecutive equations.

The third and last line contains $n$ integers $b_1 , b_2 , \dots , b_n,ドル each separated by a single space, these are the numbers on the right-hand sides of consecutive equations.

The inequality 0ドル \leq b_i \leq a_i \leq 10^{18}$ holds for each $i$ $(1 \leq i \leq n)$. The system of equations is nontrivial: $a_i \neq b_i$ holds for some $i$ $(1 \leq i \leq n)$.

출력

You should write a single integer in the first and only line of the output -- the largest $m$ for which the given system of equations is satisfied.

제한

노트

For Sample 1, system of equations $$ \left\{\begin{array}{ccc} 7 & \equiv & 3 \pmod{4} \\ 17 & \equiv & 5 \pmod{4} \\ 9 & \equiv & 1 \pmod{4} \end{array}\right. $$ is satisfied and it is easy to verify that it is not satisfied for $m > 4$.

For Sample 2, system of equations $$ \left\{\begin{array}{ccc} 4 & \equiv & 2 \pmod{1} \\ 6 & \equiv & 2 \pmod{1} \\ 5 & \equiv & 2 \pmod{1} \end{array}\right. $$ is satisfied and it is easy to verify that it is not satisfied for $m > 1$.