← 返回题目列表

Codeforces · 702/C

C. 蜂窝网络

中文机器翻译题面 查看原题

直线上有 n 个点——城市的位置(x 坐标),同一条线上的 m 个点——蜂窝塔的位置(x 坐标)。所有塔都以相同的方式工作——它们为所有城市提供蜂窝网络,这些城市距离该塔不超过r。

你的任务是找到每个城市蜂窝网络提供的最小r,即每个城市至少有一个蜂窝塔,其距离不超过r。

如果 r = 0,则塔仅为其所在点提供蜂窝网络。一座塔可以为任意数量的城市提供蜂窝网络,但所有这些城市距该塔的距离不得超过r。

输入

第一行包含两个正整数 n 和 m (1 ≤ n, m ≤ 105) — 城市数量和蜂窝塔数量。

第二行包含 n 个整数 a1, a2, ..., an (- 109 ≤ ai ≤ 109) 的序列 — 城市的坐标。同一点允许有任意多个城市。所有坐标 ai 均按非降序给出。

第三行包含 m 个整数 b1, b2, ..., bm (- 109 ≤ bj ≤ 109) 的序列 - 蜂窝塔的坐标。同一点允许有任意数量的塔。所有坐标 bj 均按非降序给出。

输出

打印最小的 r 以便每个城市都被蜂窝网络覆盖。

示例

输入 #1

3 2
-2 2 4
-3 0

输出 #1

4

输入 #2

5 3
1 5 10 14 17
4 11 15

输出 #2

3