提示: 欢迎访问OurACM平台。
Problem 1738 Minimum Distance

Accept: 59    Submit: 324
Time Limit: 2000 mSec    Memory Limit : 65536 KB

Problem Description

Clustering method requires classifying the point set in space by some way, the inter-set distance in certain class should be sufficient "near."
The general way of clustering is to select a point P, and R as distance measure, as long as the distance between point Q and point P is less than or equal to the distance R, we say that point Q and point P are in a class.
Give you N points in two-dimensional space, and a point P, you should calculate the minimum distance between the N points and the point P. The minimum distance should be not more than the distance R. The distance of Point A(x1,y1) and Point B(x2,y2) is defined as dis(A, B)=| x1-x2 |+| y1-y2 |.

Input

There are multiple test cases. For each test case, the first line contains two integers N(10≤N≤100,000) and R(1≤R≤100). N is the number of point, the minimum distance should be not more than R. The next N lines, each line contains two integers X and Y(-10000≤X,Y≤10000),(X,Y) indicates a point, these N points are all different.
The next line contains an integer Q(1≤Q≤10000), indicating the number of request. The next Q lines, each line contains two integers Px and Py(-10000≤Px,Py≤10000), indicating we should calculate the minimum distance between the N points and the point P(Px,Py). The minimum distance should be not more than the distance R. The number of points whose distance to point P(Px,Py) is not more than R is not more than 100.

Output

For each request, output the minimum distance. If the minimum distance does not exist, output “-1”.

Sample Input

5 1 1 3 2 6 5 3 -1 5 6 5 2 2 3 3 2

Sample Output

1 -1

Source

FZU 2009 Summer Training Qualification -- Hero Revival 3

Submit  Back  Status  Discuss