Johnny 是一名计算机科学专业的学生。这学期他熟练掌握了中国剩余定理。在等下一堂课的时候，他听到 Maggie 抱怨自己不会做家庭作业；一听到“模”和“方程组”这些熟悉的词汇，他立刻向这位遇到困难的少女伸出了援手。然而，Maggie 的任务与 Johnny 习惯解决的问题大不相同，它的形式如下：

$$ \begin{cases} a_1 \equiv b_1 \pmod m \\ a_2 \equiv b_2 \pmod m \\ \vdots \\ a_n \equiv b_n \pmod m \end{cases} $$

（其中 $\equiv$ 表示模同余），对于给定的 $a_1, b_1, \dots, a_n, b_n$，Maggie 需要计算出使得所有方程都成立的最大整数 $m$。Maggie 已经开始处理这些方程，并确保了对于每个 $i$ 都有 $a_i \ge b_i$。Johnny 不能失败而丢了面子——请帮他解决这个任务。

输入格式

输入的第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示方程的个数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，每个数之间用单个空格分隔，这些是连续方程左侧的数值。

第三行也是最后一行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$，每个数之间用单个空格分隔，这些是连续方程右侧的数值。

对于每个 $i$ ($1 \le i \le n$)，不等式 $0 \le b_i \le a_i \le 10^{18}$ 均成立。方程组是非平凡的：对于某些 $i$ ($1 \le i \le n$)，满足 $a_i \neq b_i$。

输出格式

你应该在输出的第一行也是唯一一行中写入一个整数——使得给定的方程组成立的最大整数 $m$。

样例

输入样例 1

3
7 17 9
3 5 1

输出样例 1

4

输入样例 2

3
4 6 5
2 2 2

输出样例 2

1

说明

对于样例 1，方程组

$$ \begin{cases} 7 \equiv 3 \pmod 4 \\ 17 \equiv 5 \pmod 4 \\ 9 \equiv 1 \pmod 4 \end{cases} $$

成立，并且很容易验证当 $m > 4$ 时它不成立。

对于样例 2，方程组

$$ \begin{cases} 4 \equiv 2 \pmod 1 \\ 6 \equiv 2 \pmod 1 \\ 5 \equiv 2 \pmod 1 \end{cases} $$

成立，并且很容易验证当 $m > 1$ 时它不成立。