Distància més petita P29245

Statement

thehtml

Donades dues col·leccions de nombres A = { a₁, …, a_n } i B = { b₁, …, b_n }, podeu calcular eficientment la mínima de les distàncies entre els n² parells (a_i, b_j)?

Per exemple, amb A = {−10, 42, 23, 6} i B = {30, −30, 1, −4} la resposta és 5, corresponent a a₄ = 6 i b₃ = 1.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb una n entre 1 i 10⁵, seguida dels n ‍nombres d’A, seguits dels n nombres de B. Tots aquests nombres es troben entre −10⁹ i 10⁹, i poden estar repetits.

Sortida

Per a cada cas, escriviu la mínima distància demanada.

Public test cases

Input

4
-10 42 23 6
30 -30 1 -4
2
1 1
6 6
1
1000000000
-1000000000
3
100 100 100
100 100 100

Output

Information

Author: Salvador Roura
Language: Catalan
Official solutions: C++
User solutions: C++