/**
 * @file 5463.cpp
 * @author Macesuted ([email protected])
 * @date 2024-10-28
 *
 * @copyright Copyright (c) 2024
 *
 */

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

#ifndef LOCAL
#define endl '\n'
#endif

bool mem1;

#define maxn 250005
#define maxlgv 28
#define B 500

typedef pair<int, int> pii;

pii a[maxn];

int64_t sqr(int64_t v) { return v * v; }
int64_t dist(int x, int y) { return sqr(a[x].first - a[y].first) + sqr(a[x].second - a[y].second); }

class Block {
   private:
    int n;
    int64_t a[maxn], b[maxn];

   public:
    Block(void) {
        for (int i = 0; i < maxn; i++) a[i] = b[i] = INT64_MAX;
    }

    void resize(int _n) { return n = _n, void(); }
    void add(int p, int64_t v) { return a[p] = min(a[p], v), b[p / B] = min(b[p / B], v), void(); }
    int64_t query(int p) {
        int64_t ans = INT64_MAX;
        int q = p;
        while (q / B == p / B) ans = min(ans, a[q++]);
        while (q / B <= n / B) ans = min(ans, b[q / B]), q += B;
        return ans;
    }
} BLK;

class Dime {
   private:
    int64_t lim;
    unordered_map<int64_t, deque<int>> list;
    queue<int> all;

    static int64_t _(int64_t x, int64_t y) { return x * int64_t(1e9) + y; }

   public:
    void setLim(int64_t v) { return lim = v, void(); }
    void insert(int p) {
        int x = a[p].first / lim / 2, y = a[p].second / lim / 2, del = 0;
        for (int tx = x - 1; tx <= x + 1; tx++)
            for (int ty = y - 1; ty <= y + 1; ty++)
                if (list.find(_(tx, ty)) != list.end())
                    for (auto q : list[_(tx, ty)]) {
                        int64_t d = dist(p, q);
                        BLK.add(q, d);
                        if (d < lim) del = q;
                    }

        while (!all.empty() && all.front() <= del) {
            int q = all.front();
            all.pop();
            int tx = a[q].first / lim / 2, ty = a[q].second / lim / 2;
            list[_(tx, ty)].pop_front();
            if (list[_(tx, ty)].empty()) list.erase(_(tx, ty));
        }

        list[_(x, y)].push_back(p), all.push(p);
        return;
    }
};

Dime dims[maxlgv];
vector<pii> ques[maxn];
int64_t ans[maxn];

void solve(void) {
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i].first >> a[i].second;
    for (int i = 1, l, r; i <= q; i++) cin >> l >> r, ques[r].emplace_back(l, i);

    for (int i = 0; i < maxlgv; i++) dims[i].setLim((int64_t)1 << i);
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < maxlgv; j++) dims[j].insert(i);
        for (auto [l, id] : ques[i]) ans[id] = BLK.query(l);
    }

    for (int i = 1; i <= q; i++) cout << ans[i] << endl;
    return;
}

bool mem2;

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
#ifdef LOCAL
    cerr << "Memory Cost: " << abs(&mem1 - &mem2) / 1024. / 1024. << "MB" << endl;
#endif

    int _ = 1;
    while (_--) solve();

#ifdef LOCAL
    cerr << "Time Cost: " << clock() * 1000. / CLOCKS_PER_SEC << "MS" << endl;
#endif
    return 0;
}