Apples and Apple Trees

Interview

Time limit1sMemory limit128 MB

Summary

Given positions of n trees and m apples on a line, find the minimum distance from any apple to its nearest tree.

Level: Medium5 of 10
Topics: Sorting, Binary search, Array, Two pointers
Solved: No attempts yet

Problem

There is a well-known Polish proverb: "An apple always falls near the apple tree." Let us verify this proverb experimentally.

To keep things simple, assume that all apple trees and apples lie on a single line, so each position can be described by a single coordinate. Assume also that every apple fell from the apple tree closest to it.

For each apple you can consider the distance to the tree it fell from (that is, to the nearest apple tree). Write a program that:

reads the positions of the apple trees and the apples from standard input,
computes the smallest of these distances over all apples,
writes the result to standard output.

(An English equivalent of this proverb is "Like father, like son" or "Like mother, like daughter.")

Input

The first line contains two integers $n$ and $m$ ( $1 \le n, m \le 100\,000$ ), separated by a single space, denoting the number of apple trees and the number of apples.

The second line contains $n$ integers, separated by single spaces, giving the coordinates of the apple trees. Each coordinate is an integer in the range $[0, 10^8]$ .

The third line contains $m$ integers, separated by single spaces, giving the coordinates of the apples. Each coordinate is an integer in the range $[0, 10^8]$ .

Both apple trees and apples are treated as points on a line, and several apple trees or several apples may share the same point.

Output

Output a single line containing the smallest distance between an apple and the apple tree closest to it.

Examples3

Example 1
Input
```
3 5
10 1 4
2 2 5 7 8
```
Expected output
```
1
```
Example 2
Input
```
1 1
5
5
```
Expected output
```
0
```
Example 3
Input
```
1 1
0
100000000
```
Expected output
```
100000000
```