Cipele

Time limit1sMemory limit64 MB

Summary

Match as many left/right shoe pairs as possible, as long as no further pair can be formed, and minimize the largest size gap.

Level: Medium7 of 10
Topics: Binary search, Graph, Two pointers, Greedy
Solved: No attempts yet

Problem

After spending most of his money on various projects, Nadan decided to buy 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 is important that no new pair can be selected after all the shoes are paired. Each pair must consist of one left shoe and one right shoe. While pairing the shoes, you must make sure that the ugliness is minimized. The ugliness of one pairing is defined as the maximal absolute difference of the shoe sizes over all pairs of shoes.

Input

The first line contains two positive integers N and M (1 ≤ N, M ≤ 100 000), the number of left shoes and right shoes, in that order.

The second line contains N numbers Li (1 ≤ Li ≤ 109), the sizes of the left shoes.

The third line contains M numbers Ri (1 ≤ Ri ≤ 109), the sizes of the right shoes.

Output

Output the minimal ugliness over all possible shoe pairings.

Examples3

Example 1
Input
```
2 3
2 3
1 2 3
```
Expected output
```
0
```
Example 2
Input
```
4 3
2 39 41 45
39 42 46
```
Expected output
```
1
```
Example 3
Input
```
5 5
7 6 1 2 10
9 11 6 3 12
```
Expected output
```
4
```