102122: [AtCoder]ABC212 C - Min Difference

Problem Statement

You are given two sequences: $A=(A_1,A_2, \ldots ,A_N)$ consisting of $N$ positive integers, and $B=(B_1, \ldots ,B_M)$ consisting of $M$ positive integers.

Find the minimum difference of an element of $A$ and an element of $B$, that is, $\displaystyle \min_{ 1\leq i\leq N}\displaystyle\min_{1\leq j\leq M} \lvert A_i-B_j\rvert$.

Constraints

• $1 \leq N,M \leq 2\times 10^5$
• $1 \leq A_i \leq 10^9$
• $1 \leq B_i \leq 10^9$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $M$
$A_1$ $A_2$ $\ldots$ $A_N$
$B_1$ $B_2$ $\ldots$ $B_M$

Output

Print the answer.

Sample Input 1

2 2
1 6
4 9

Sample Output 1

2

Here is the difference for each of the four pair of an element of $A$ and an element of $B$: $\lvert 1-4\rvert=3$, $\lvert 1-9\rvert=8$, $\lvert 6-4\rvert=2$, and $\lvert 6-9\rvert=3$. We should print the minimum of these values, or $2$.

Sample Input 2

1 1
10
10

Sample Output 2

0

Sample Input 3

6 8
82 76 82 82 71 70
17 39 67 2 45 35 22 24

Sample Output 3

3

问题描述

给你两个序列：$A=(A_1,A_2, \ldots ,A_N)$，包含$N$个正整数，和$B=(B_1, \ldots ,B_M)$，包含$M$个正整数。

找到$A$和$B$中的一个元素之间的最小差值，即$\displaystyle \min_{ 1\leq i\leq N}\displaystyle\min_{1\leq j\leq M} \lvert A_i-B_j\rvert$。

约束

• $1 \leq N,M \leq 2\times 10^5$
• $1 \leq A_i \leq 10^9$
• $1 \leq B_i \leq 10^9$
• 输入中的所有值都是整数。

输入

输入通过标准输入给出，格式如下：

$N$ $M$
$A_1$ $A_2$ $\ldots$ $A_N$
$B_1$ $B_2$ $\ldots$ $B_M$

输出

打印答案。

样例输入1

2 2
1 6
4 9

样例输出1

2

这是$A$和$B$中每一对元素之间的差值：$\lvert 1-4\rvert=3$，$\lvert 1-9\rvert=8$，$\lvert 6-4\rvert=2$，和$\lvert 6-9\rvert=3$。我们应该打印这些值中的最小值，即$2$。

样例输入2

1 1
10
10

样例输出2

0

样例输入3

6 8
82 76 82 82 71 70
17 39 67 2 45 35 22 24

样例输出3

3