#include <bits/stdc++.h>
using namespace std;
const int MAXN = 250005, B = 500;
int n, q;
int x[MAXN], y[MAXN];
vector<pair<int, int>> qs[MAXN];
long long dis(int i, int j) { return 1ll * (x[i] - x[j]) * (x[i] - x[j]) + 1ll * (y[i] - y[j]) * (y[i] - y[j]); }
long long ans[MAXN];
unordered_map<long long, pair<int, int>> mp;
int L[MAXN], R[MAXN], bl[MAXN];
long long val[MAXN], valb[MAXN];
void add(int d, long long v) { val[d] = min(val[d], v), valb[bl[d]] = min(valb[bl[d]], v); }
long long query(int l, int r) {
    long long ans = LLONG_MAX;
    for (int i = l; i <= R[bl[l]]; i++) ans = min(ans, val[i]);
    r = bl[r];
    for (int i = bl[l] + 1; i <= r; i++) ans = min(ans, valb[i]);
    return ans;
}
vector<int> pts[MAXN];
int p[MAXN];
int bx[MAXN], by[MAXN];
long long id(int x, int y) { return ((x + 5ll) << 30) | (y + 5ll); }
int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) scanf("%d%d", &x[i], &y[i]);
    for (int i = 1; i <= q; i++) {
        int l, r; scanf("%d%d", &l, &r);
        qs[r].push_back({ l, i });
    }
    for (int l = 1, r, i = 1; l <= n; l = r + 1, i++) {
        r = min(n, l + B - 1);
        L[i] = l, R[i] = r;
        for (int j = l; j <= r; j++) bl[j] = i;
    }
    auto ins = [&](int i, int s, int r) {
        for (int j = s + 1; j <= s + 3 && j < r; j++) {
            // printf("(%d, %d)\n", p[i], p[j]);
            if (p[i] < p[j]) pts[p[j]].push_back(p[i]);
            else pts[p[i]].push_back(p[j]);
        }
    };
    memset(val, 0x3f, sizeof val);
    memset(valb, 0x3f, sizeof valb);
    for (int k = 0; k <= 29; k++) {
        for (int i = 1; i <= n; i++) p[i] = i, bx[i] = x[i] >> k, by[i] = y[i] >> k;
        sort(p + 1, p + 1 + n, [&](int i, int j) { return bx[i] == bx[j] ? by[i] < by[j] : bx[i] < bx[j]; });
        for (int l = 1, r; l <= n; l = r) {
            while (r <= n && bx[p[l]] == bx[p[r]] && by[p[l]] == by[p[r]]) r++;
            int X = bx[p[l]], Y = by[p[l]];
            mp[id(X, Y)] = { l, r };
            for (int i = l; i < r; i++) ins(i, i, r);
        }
        for (int l = 1, r; l <= n; l = r) {
            while (r <= n && bx[p[l]] == bx[p[r]] && by[p[l]] == by[p[r]]) r++;
            int X = bx[p[l]], Y = by[p[l]];
            for (auto [dx, dy] : vector<pair<int, int>>{ {-1, 1}, {0, 1}, {1, 1}, {1, 0} }) {
                if (!mp.count(id(X + dx, Y + dy))) continue;
                auto [pl, pr] = mp[id(X + dx, Y + dy)];
                int px = l, py = pl;
                while (px != r && py != pr) {
                    if (p[px] < p[py]) ins(px, py, pr), px++;
                    else ins(py, px, r), py++;
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (auto p : pts[i]) add(p, dis(p, i));
        for (auto p : qs[i]) ans[p.second] = query(p.first, i);
    }
    for (int i = 1; i <= q; i++) printf("%lld\n", ans[i]);
    return 0;
}