시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 512 MB | 10 | 1 | 1 | 10.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.
10 1 15 6 4 2 4 6 18 1 20 6 9 0 9 7 9 0 1 6 3
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.