Độ chênh lệch nhỏ nhất (Min Difference)

Nguồn: AtCoder

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

Đề bài

Cho hai dãy số nguyên dương:

$$A=(A_1,A_2,\ldots,A_N)$$

gồm $N$ phần tử và

$$B=(B_1,B_2,\ldots,B_M)$$

gồm $M$ phần tử.

Ta chọn:

• một phần tử $A_i$ từ dãy $A$;
• một phần tử $B_j$ từ dãy $B$.

Độ chênh lệch giữa hai phần tử được chọn là giá trị tuyệt đối:

$$|A_i-B_j|.$$

Hãy tìm độ chênh lệch nhỏ nhất có thể khi chọn một phần tử từ mỗi dãy.

Nói cách khác, cần tính:

$$\min_{1\le i\le N}\min_{1\le j\le M}|A_i-B_j|.$$

Nếu hai dãy có ít nhất một cặp phần tử bằng nhau thì độ chênh lệch nhỏ nhất bằng $0$.

Input

Dòng đầu tiên chứa hai số nguyên $N$ và $M$ — lần lượt là số phần tử của dãy $A$ và dãy $B$.

Dòng thứ hai chứa $N$ số nguyên:

$$A_1,A_2,\ldots,A_N.$$

Dòng thứ ba chứa $M$ số nguyên:

$$B_1,B_2,\ldots,B_M.$$

Output

In ra một số nguyên — giá trị nhỏ nhất của:

$$|A_i-B_j|$$

trên mọi cách chọn $1\le i\le N$ và $1\le j\le M$.

Subtask

• Subtask 1 — 30% — Time Limit: 2.00 s: $1\le N,M\le 2000$; $1\le A_i,B_j\le 10^9$.
• Subtask 2 — 70% — Time Limit: 2.00 s: $1\le N,M\le 2\cdot10^5$; $1\le A_i,B_j\le 10^9$.

Ví dụ

Ví dụ 1

Input

2 2
1 6
4 9

Output

2

Giải thích

Dãy $A$ gồm:

$$[1,6]$$

và dãy $B$ gồm:

$$[4,9].$$

Có bốn cách chọn một phần tử từ mỗi dãy:

• chọn $1$ và $4$: $|1-4|=3$;
• chọn $1$ và $9$: $|1-9|=8$;
• chọn $6$ và $4$: $|6-4|=2$;
• chọn $6$ và $9$: $|6-9|=3$.

Giá trị nhỏ nhất trong các độ chênh lệch trên là:

$$2.$$

Vì vậy kết quả là 2.

Ví dụ 2

Input

1 1
10
10

Output

0

Giải thích

Hai dãy đều chỉ chứa phần tử $10$.

Chọn hai phần tử này, ta có:

$$|10-10|=0.$$

Độ chênh lệch không thể nhỏ hơn $0$, do đó đáp án là:

$$0.$$

Ví dụ 3

Input

6 8
82 76 82 82 71 70
17 39 67 2 45 35 22 24

Output

3

Giải thích

Trong dãy $A$ có phần tử $70$, còn trong dãy $B$ có phần tử $67$.

Độ chênh lệch của cặp này là:

$$|70-67|=3.$$

Không tồn tại cặp phần tử nào, với một phần tử lấy từ $A$ và một phần tử lấy từ $B$, có độ chênh lệch nhỏ hơn $3$.

Vì vậy đáp án là:

$$3.$$