Mạng di động (Cellular Network)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $n$ thành phố và $m$ trạm phát sóng nằm trên cùng một đường thẳng.

Tọa độ các thành phố là

và tọa độ các trạm phát sóng là

Một trạm đặt tại $b_j$ phủ sóng một thành phố đặt tại $a_i$ khi khoảng cách giữa hai điểm không vượt quá bán kính $r$:

Tất cả trạm sử dụng cùng một bán kính $r$. Hãy tìm giá trị nguyên nhỏ nhất của $r$ sao cho mỗi thành phố được ít nhất một trạm phủ sóng.

Nếu $r=0$, một trạm chỉ phủ đúng những thành phố nằm cùng tọa độ với nó. Một trạm có thể phủ bất kỳ số lượng thành phố nào miễn là từng thành phố đều cách trạm không quá $r$.

Input

• Dòng đầu chứa hai số nguyên $n,m$.
• Dòng thứ hai chứa $n$ tọa độ $a_1,a_2,\ldots,a_n$ theo thứ tự không giảm.
• Dòng thứ ba chứa $m$ tọa độ $b_1,b_2,\ldots,b_m$ theo thứ tự không giảm.

Output

In bán kính nguyên nhỏ nhất $r$ để tất cả thành phố đều được phủ sóng.

Subtask

• Subtask 1 — 20%: $1\le n,m\le100$.
• Subtask 2 — 30%: $1\le n,m\le5000$.
• Subtask 3 — 50%: $1\le n,m\le10^5$, $-10^9\le a_i,b_j\le10^9$. Nhiều thành phố hoặc nhiều trạm có thể nằm cùng một tọa độ.

Ví dụ

Input

3 2
-2 2 4
-3 0

Output

4

Giải thích

Khoảng cách từ các thành phố $-2,2,4$ đến trạm gần nhất lần lượt là $1,2,4$. Vì vậy mọi bán kính nhỏ hơn $4$ đều bỏ sót thành phố tại $4$, còn $r=4$ phủ được cả ba thành phố.