Largest Good Square Region

Given $n$ distinct points on the plane and $m$ queries, you are to answer the following: A region (square) is defined as (good) if and only if it is a square with sides parallel to the coordinate axes and there is no given point that is strictly contained in it. A point (A=(x_A,y_A)) is said to be strictly contained in a square (B) if (A) lies in the interior of (B) (i.e. not on its boundary).

For each query you are given a point (Q=(x,y)). Your task is to find the side length of the largest good square region that strictly contains (Q). If the square side length can be arbitrarily large, output (-1).

Note that you can choose the placement of your square arbitrarily as long as:

1. Its sides are parallel to the coordinate axes.
2. The square strictly contains the query point (Q=(x,y)) (i.e. (Q) lies in the interior, not on the boundary).
3. There is no given point that lies strictly inside the square (points may lie on the boundary).

A crucial simplification is that all the (n+m) points are in general position, meaning that all x-coordinates are distinct and all y-coordinates are distinct.

inputFormat

The first line contains two integers (n) and (m) (the number of given points and the number of queries).

Each of the next (n) lines contains two integers representing the coordinates of a given point.

Each of the following (m) lines contains two integers (x) and (y) representing a query point.

It is guaranteed that all the (n+m) points have distinct x-coordinates and distinct y-coordinates.

outputFormat

For each query, output a single integer: the side length of the largest good square region that strictly contains the query point. If the side length can be arbitrarily large, output (-1).

sample

3 1
1 100
10 1
50 50
5 60

9