Sau khi siêu bão YAGI đi qua, làng Nủ được xây dựng lại \(n\) ngôi nhà và \(m\) cột đèn trên cùng một trục đường (có thể xem là một trục tọa độ). Nhưng do địa hình miền núi nên khoảng cách giữa các cột đèn và giữa các ngôi nhà là khác nhau. Tý được giao lắp đặt các bóng đèn đường để mỗi ngôi nhà của làng Nủ đều được chiếu sáng bởi ít nhất \(1\) bóng đèn đường. Tuy nhiên, mỗi loại bóng đèn lại có cường độ chiếu sáng khác nhau, mà Tý lại muốn lắp đặt cùng một loại bóng đèn đường nên Tý đang phân vân không biết nên chọn loại bóng đèn đường có cường độ chiếu sáng tối thiểu là bao nhiêu.
Yêu cầu: Cho biết tọa độ của \(n\) ngôi nhà và \(m\) cột đèn. Hãy giúp Tý tìm loại bóng đèn đường có cường độ chiếu sáng d nhỏ nhất đáp ứng yêu cầu trên. Biết, ngôi nhà được chiếu sáng nếu khoảng cách đến cột đèn gần nhất \(\leq d\).
INPUT
- Dòng \(1\): Gồm \(1\) số nguyên dương \(n\) \((1 \leq n \leq 10^5)\);
- Dòng \(2\): Gồm \(n\) số nguyên \(a_1, a_2, ..., a_n\) \((-10^9\leq a_i \leq 10^9)\) là tọa độ của \(n\) ngôi nhà;
- Dòng \(3\): Gồm \(1\) số nguyên dương \(m\) \((1 \leq m \leq 10^5)\);
- Dòng \(4\): Gồm \(m\) số nguyên \(b_1, b_2, ..., b_m\) \((-10^9\leq b_i \leq 10^9)\) là tọa độ của m cột đèn.
OUTPUT
- In ra một số nguyên \(d\) duy nhất tìm được
Example
Test 1
Input
3
-2 2 4
2
-3 0
Output
4
Ràng buộc
- Subtask \(1\) (\(60\%\) test): Có \((1 \leq n \leq m \leq 10^4)\)
- Subtask \(2\) (\(40\%\) test): Có \((1 \leq n \leq m \leq 10^5)\)
Bình luận