Competitions

# Shoes

After spending most of his money on various projects, Nadan decided to afford high quality shoes for his software developers. Luckily for Nadan, he found n left shoes and m right shoes in his basement. Since their origin is unknown, the shoes come in various sizes.

Nadan asked you to pair as many shoes as possible (it’s important that a new pair cannot be selected after pairing all the shoes). Each pair should consist of one left shoe and one right shoe. While pairing the shoes, you should make sure that the ugliness is minimized. The ugliness of one pairing is defined as the maximal absolute difference of the shoe sizes between all pairs of shoes.

#### Input

The first line contains two positive integers n and m (1n, m105), the number of left shoes and right shoes, in that order.

The second line contains n numbers li (1li109), the sizes of the left shoes.

The third line contains m numbers ri (1 ≤ ri109), the sizes of the right shoes.

#### Output

Print the minimal ugliness between all possible shoe pairings.

#### Explanation

Consider the clarification of the second test.

Nadan has 4 left and 3 right shoes, maximal number of pairs that can be obtained is 3. One possible pairing is: 39 - 46 , 41 - 42, 45 - 39, but ugliness of such pairing is 7 because of the first pair.

Better pairing would be: 39 - 39, 41 - 42, 45 - 46, with ugliness being equal to 1, which is minimal possible ugliness that can be obtained.

Time limit 1 second
Memory limit 128 MiB
Input example #1
2 3
2 3
1 2 3

Output example #1
0

Input example #2
4 3
2 39 41 45
39 42 46

Output example #2
1

Input example #3
5 5
7 6 1 2 10
9 11 6 3 12

Output example #3
4

Source 2018 COCI Round 1, October 20