#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, q;
    cin >> n >> q;
    vector<array<int, 2>> a(n);
    for (auto &p : a) {
        cin >> p[0] >> p[1];
    }
    auto sqr = [&](ll x) {
        return x * x;
    };
    while (q--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        int dist = abs(x1 - x2) + abs(y1 - y2);
        auto chk = [&](int lim) {
            long long r1 = 1LL * (lim + 1) * (lim + 1);
            long long r2 = 1LL * (lim + dist + 1) * (lim + dist + 1);
            for (auto &p : a) {
                if (sqr(p[0] - x1) + sqr(p[1] - y1) <= r1) return 0;
                if (sqr(p[0] - x2) + sqr(p[1] - y2) <= r2) return 0;
            }
            return 1;
        };
        int l = 0, r = 1e7, ans = -1;
        while (l <= r) {
            int mid = (l + r) / 2;
            chk(mid) ? l = (ans = mid) + 1 : r = mid - 1;
        }
        cout << ans << "\n";
    }
    return 0;
}