思路

暴力解法是遍历数组 $A$ 中的每个元素 $x$ 和数组 $B$ 中的每个元素 $y$，计算 $(x + y) \pmod{mod}$ 并找到最小值。这种方法的时间复杂度是 $O(n \times m)$。考虑到 $n$ 和 $m$ 的最大值可达 $100000$，$n \times m$ 最大会达到 $10^{10}$，这显然会超时。因此，我们需要一个更高效的算法。

我们可以优化查找过程。首先，$(x + y) \pmod{mod}$ 的值等价于 $((x \pmod{mod}) + (y \pmod{mod})) \pmod{mod}$。所以我们可以先将两个数组中的所有元素都对 $mod$ 取模，这不会影响最终结果，但可以使数值处理更方便。

接下来，我们固定数组 $A$ 中的一个元素 $x$，然后尝试在数组 $B$ 中寻找一个最优的 $y$ 来与之配对。设 $a = x \pmod{mod}$，我们希望找到一个 $b = y \pmod{mod}$，使得 $(a + b) \pmod{mod}$ 最小。

为了让 $(a + b) \pmod{mod}$ 的值尽可能小，有两种主要情况：

题目内容

给你一个长度为 $n$ 的数组 $A$ 和一个长度为 $m$ 的数组 $B$ ，以及一个模数 $mod$ ，你需要从数组 $A$ 里选取一个数 $x$ ，从数组 $B$ 中选取一个数 $y$ ，使得 $(x+y)$%$mod$的值是所有选取方式中最小的，输出这个最小值即可。

输入描述

第一行三个整数 $n,m,mod$ ，分别表示 $A$ 数组的长度、$B$ 数组的长度以及模数。

第二行 $n$ 个整数，第 $1$ 个数表示 $A$ 数组中第 $1$ 个数的大小。

第三行 $m$ 个整数，第 $i$ 个数表示 $B$ 数组中第 $i$ 个数的大小。

$1<=n,m<=100000$

$1 <= A[i],B[i], mod <=10^{18}$

输出描述

一个整数 $x$ ，表示求得的最小值。

样例1

输入

4 5 10
2 3 4 5
1 2 3 4 6

输出

0

样例2

输入

2 2 100000000007
27234626274 344569274255
9237235275 23974652709327

输出

1887413921