C. Сүлжээ

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Танд шулуун шугаман дээр $n$ ширхэг цэг өгөгдөх бөгөөд эдгээр нь хотуудын байрлал ($x$-координатууд). Адилхан шугаман дээр $m$ ширхэг цэг өгөгдөх бөгөөд эдгээр нь сүлжээний цамхагийн байрлал ($x$-координатууд). Бүх цамхагууд адил зарчмаар ажилладаг бөгөөд цамхагууд $r$ зайнд орших бүх хотод сүлжээг түгээдэг.

Таны даалгавар бол хот болгон сүлжээгээр хангагдсан байхаар хамгийн бага $r$-ыг олох юм.

Хэрвээ $r = 0$ бол цамхаг зөвхөн байрлах газраа сүлжээг түгээдэг. Нэг цамхаг хэдэн ч хотын сүлжээг хангаж болно. Гэхдээ энэ бүх хотууд цамхагаас $r$-ээс их зайнд байрлаж болохгүй.

Оролт

Эхний мөрөнд 2 ширхэг эерэг бүхэл тоонууд $n$ ба $m$ ($1 ≤ n, m ≤ 10^{5}$) өгөгдөнө. Эдгээр нь хотуудын тоо болон сүлжээний цамхагийн тоо юм.

2 дахь мөрөнд $n$ ширхэг бүхэл тоонууд $a_{1}, a_{2}, ..., a_{n}$ ($ - 10^{9} ≤ a_{i} ≤ 10^{9}$) өгөгдөнө. Эдгээр нь хотуудын координат. Нэг цэгт олон тоо хотууд байрлаж болно. Бүх координатууд $a_{i}$ буурахгүй дарааллаар өгөгдсөн.

3 дахь мөрөнд $m$ ширхэг бүхэл тоонууд $b_{1}, b_{2}, ..., b_{m}$ ($ - 10^{9} ≤ b_{j} ≤ 10^{9}$) өгөгдөнө. Эдгээр нь сүлжээний цамхагийн координатууд. Нэг цэгт олон тооны цамхагууд байж болно. Бүх координатууд $b_{j}$ буурахгүй дарааллаар өгөгдсөн.

Гаралт

Хот болгон сүлжээгээр хангагдсан байхаар хамгийн бага $r$-ийг хэвлэнэ үү.

Орчуулсан: Энхлут

Жишээ тэстүүд

Оролт
3 2
-2 2 4
-3 0
Гаралт
4
Оролт
5 3
1 5 10 14 17
4 11 15
Гаралт
3
Сэтгэгдлүүдийг ачааллаж байна...