시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 0 0 0 0.000%

문제

Yuuka has $n$ integers $a_1, a_2, \dots, a_n$ generated uniformly and independently between $1$ and $10^{18}$, inclusive.

Yuuka chooses an integer $m$. Next, an integer $k$ is generated uniformly between $0$ and $(m - 1)$, inclusive. After that, Yuuka changes every $a_i$ to $(a_i + k) \bmod m$. Finally, she randomly shuffles the integers. The resulting integers are $b_1, b_2, \ldots, b_n$.

Now, given $a_1, a_2, \ldots, a_n$ and $b_1, b_2, \ldots, b_n$, you need to figure out the values of $m$ and $k$.

입력

The first line contains an integer $n$, the number of integers ($10^5 \le n \le 2 \cdot 10^5$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$: the $n$ randomly generated integers ($1 \le a_i \le 10^{18}$).

The third line contains $n$ integers $b_1, b_2, \dots, b_n$: the resulting integers ($0 \le b_i < 10^{10}$).

It is guaranteed that there exists a solution such that $0 \le k < m \le 10^{10}$.

출력

Output two integers $m$ and $k$ on a single line. If there are several possible answers, output any one of them.

예제 입력 1

10
1 15 6 4 2 4 6 18 1 20
6 9 0 9 7 9 0 1 6 3

예제 출력 1

11 5

힌트

Please note that the example in the problem statement is only to show the format! The tests in the system will not include this example (test 1 will be some other test), as it violates the constraints.