Problem Description

After spending funds on various projects, Nadan has decided to provide high-quality shoes for software developers.

Nadan found $N$ left shoes and $M$ right shoes in the basement. Due to their unknown origin, the sizes of the shoes vary.

Nadan wants you to pair up as many shoes as possible (i.e., no more pairs can be formed after all shoes are paired). Each pair should consist of one left shoe and one right shoe. When wearing a pair of shoes, the goal is to minimize the ugliness of the shoes. The ugliness of a pair of shoes is defined as the maximum absolute difference in sizes between the left and right shoes among all paired shoes.

Input Format

The first line contains two positive integers $N$ and $M$, representing the number of left shoes and right shoes, respectively.

The second line contains $N$ integers $L_i$, representing the sizes of the left shoes.

The third line contains $M$ integers $R_i$, representing the sizes of the right shoes.

Output Format

Output the minimum ugliness among all possible pairing methods.

Sample Input and Output

Sample Input #1

2 3
2 3
1 2 3

Sample Output #1

0

Sample Input #2

4 3
2 39 41 45
39 42 46

Sample Output #2

1

Sample Input #3

5 5
7 6 1 2 10
9 11 6 3 12

Sample Output #3

4

Notes

Sample 2 Explanation

Nadan has 4 left shoes and 3 right shoes, and can form at most 3 pairs. One pairing method is: 39-46, 41-42, 45-39, where the pair with the largest absolute difference in sizes is the first pair, resulting in an ugliness of 7.

A better pairing method is: 39-39, 41-42, 45-46. This pairing method has an ugliness of 1, which is the minimum among all pairing methods.

Data Size and Constraints

For 20% of the data, $N = M$.

For another 50% of the data, $N, M \le 5000$.

For 100% of the data, $1 \le N, M \le 10^5$, $1 \le L_i, R_i \le 10^9$.

Notes

This problem's score is set according to the original COCI contest, with a full score of 90.

The problem is translated from COCI2018-2019 CONTEST #1 T3 Cipele.

见题面 Input 部分

见题面 Output 部分