Near 2

A well-known Polish proverb says: "The apple always falls near the apple tree." Your task is to test this proverb experimentally.

The positions of the apple trees and the apples are points on a plane. The distance between two points is measured with the Manhattan metric:

$d((x_1, y_1), (x_2, y_2)) = |x_1 - x_2| + |y_1 - y_2|$

Assume that every apple has fallen from the apple tree that is closest to it.

Write a program that:

• reads the positions of the apple trees and the apples from standard input,
• computes the smallest distance between an apple and the apple tree it fell from,
• writes that distance to standard output.

(In English, an equivalent proverb is "Like father, like son" or "Like mother, like daughter.")

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

The second line contains $2n$ integers in the range $[0, 10^8]$, separated by single spaces, giving the coordinates of the apple trees: $x_1\ y_1\ x_2\ y_2\ \dots\ x_n\ y_n$.

The third line contains $2m$ integers in the range $[0, 10^8]$, separated by single spaces, giving the coordinates of the apples: $x'_1\ y'_1\ x'_2\ y'_2\ \dots\ x'_m\ y'_m$.

Both apple trees and apples are treated as points on the plane, and several apple trees or several apples may lie on the same point.

Print a single integer: the smallest distance between an apple and the apple tree it fell from.