///一道结论题：若公主在找到王子的途中就碰到月亮，则公主之后每一秒都会碰到这个月亮。

///证明：设公主在ts的时候处于A点，碰到了圆心为B点，半径为r的月亮。
///这就说明：AB <= r。
///假设公主在(t + 1)s的时候移动到了A'点，且A'A = 1, 则r + 1 >= A’A + AB >= A'B, 即公主在(t + 1)s也能够碰到这个月亮。
///由数学归纳法可知原结论成立！ Q.E.D

///为什么这个结论很重要呢？ 因为有了这个结论，就可以不用维护公主找到王子途中的信息，直接考虑王子所在点的信息即可。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#define INF 10000000010
#define MAXN 1010
using namespace std;

inline long long read() {
    register long long x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

long long n, q;
struct node {
    long long x, y;
} Orz_Chengchunhao[MAXN];

inline long long Orz_Sunzhihao(long long a_x, long long a_y, long long b_x, long long b_y) {
    long long ans = sqrt((a_x - b_x) * (a_x - b_x) + (a_y - b_y) * (a_y - b_y));
    if (ans * ans == (a_x - b_x) * (a_x - b_x) + (a_y - b_y) * (a_y - b_y)) ans--;
    return ans;
}

int main() {
    n = read(); q = read();
    for (long long i = 1; i <= n; i++) {
        Orz_Chengchunhao[i].x = read();
        Orz_Chengchunhao[i].y = read();
    }
    for (long long i = 1; i <= q; i++) {
        long long px = read(), py = read(), qx = read(), qy = read();
        long long dist = abs(qx - px) + abs(qy - py), minn = INF;
        for (long long j = 1; j <= n; j++) {
            minn = min(minn, Orz_Sunzhihao(qx, qy, Orz_Chengchunhao[j].x, Orz_Chengchunhao[j].y) - 1);
        }
        minn = max(minn - dist, (long long)(-1));
        printf("%lld\n", minn);
    }
    return 0;
}