Distance to the nearest point P28079

Given two sets $S$ and $Q$ of points on the plane, determine, for each point in $Q$, the minimum of the Manhattan distances to the points in $S$.

Input

Input consists of a natural $n$, the coordinates of the $n$ points in $S$, a natural $m$, and the coordinates of the $m$ points in $Q$. Assume $1 \le n \le 10^5$ and $0 \le m \le 10^5$. The coordinates are real numbers. Points can be repeated.

Output

For every point in $Q$, print the Manhattan distance to its closest point in $S$.

Observation

This problem tolerates an error of $10^{-7}$ for each output.