题目描述

给定两个正整数数组：数组 $L$ 包含 $N$ 个元素，数组 $R$ 包含 $M$ 个元素。

你需要从这两个数组中选出尽可能多的元素进行一一配对，即恰好配对 $\min(N, M)$ 对元素。每一对必须包含一个 $L$ 中的元素和一个 $R$ 中的元素，且每个元素最多只能被配对一次。

定义一种配对方案的“代价”为：所有配对元素对中，两数之差的绝对值的最大值。换句话说，如果第 $k$ 对元素分别是 $L_{x_k}$ 和 $R_{y_k}$，则该方案的代价为 $\max \{ |L_{x_k} - R_{y_k}| \}$。

请你求出在所有合法的配对方案中，代价的最小值。

输入格式

第一行包含两个正整数 $N, M$ —— 分别表示数组 $L$ 和数组 $R$ 的长度。

第二行包含 $N$ 个正整数 $L_1, L_2, \dots, L_N$ —— 表示数组 $L$ 的元素。

第三行包含 $M$ 个正整数 $R_1, R_2, \dots, R_M$ —— 表示数组 $R$ 的元素。

输出格式

输出一行，一个整数，表示在所有配对方式中，代价的最小值。

样例输入 1

2 3
2 3
1 2 3

样例输出 1

0

样例输入 2

4 3
2 39 41 45
39 42 46

样例输出 2

1

样例输入 3

5 5
7 6 1 2 10
9 11 6 3 12

样例输出 3

4

说明

样例解释

在样例 $2$ 中，$N=4, M=3$，最多可以配对 $\min(4, 3) = 3$ 对。

• 一种较差的配对方式为 $(39, 46), (41, 42), (45, 39)$，其中差的绝对值最大为 $|39 - 46| = 7$，代价为 $7$。
• 最优的配对方式为 $(39, 39), (41, 42), (45, 46)$。这三对元素差的绝对值分别为 $|39 - 39| = 0$，$|41 - 42| = 1$，$|45 - 46| = 1$，最大值为 $1$。因此代价为 $1$，这是所有配对方案中代价的最小值。

数据范围

• 对于 $20\%$ 的数据，保证 $N = M$。
• 对于另外 $50\%$ 的数据，保证 $1 \le N, M \le 5000$。
• 对于 $100\%$ 的数据，保证 $1 \le N, M \le 10^5$。
• 对于 $100\%$ 的数据，保证 $1 \le L_i, R_i \le 10^9$。
• 保证所有的输入数值均为整数。