// just for test
#include <bits/stdc++.h>
using namespace std;
using i64=long long; const int N=2.5e5+5;
namespace DS {
    const i64 INF=1e18;
    const int block=500;
    i64 t1[N],t2[N];
    void clear() { for (int i=0;i<N;i++) t1[i]=t2[i]=INF; }
    void add(int x,i64 d) {
        t1[x]=min(t1[x],d);
        t2[x/block]=min(t2[x/block],d);
    }
    i64 query(int l,int r) {
        i64 res=INF;
        if (r/block==l/block) {
            for (int i=l;i<=r;i++) res=min(res,t1[i]);; return res;
        }
        for (int i=l;i<(l/block+1)*block;i++) res=min(res,t1[i]);
        for (int i=r/block*block;i<=r;i++) res=min(res,t1[i]);
        for (int i=l/block+1;i<r/block;i++) res=min(res,t2[i]);
        return res;
    }
};
int n,q; i64 x[N],y[N]; double xx[N]; i64 ans[N]; int ord[N],rev[N]; vector<pair<int,int>> qry[N]; mt19937 rnd(190345);
i64 get_dis(int i,int j) { return (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]); }
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) cin >> x[i] >> y[i];
    for (int i = 1; i <= q; ++i) {
        int l, r; cin >> l >> r;
        qry[r].push_back({l, i});
    }
    double len = (rnd() % 100000000 + 1) / 100000000.0 * 2 * acos(-1.0);
    double Sin = sin(len), Cos = cos(len);
    for (int i = 1; i <= n; ++i) xx[i] = x[i] * Cos - y[i] * Sin, ord[i] = i;
    sort(ord + 1, ord + n + 1, [&](int i, int j) {
        return xx[i] < xx[j];
    });
    for (int i = 1; i <= n; ++i) rev[ord[i]] = i;
    DS::clear();
    for (int i = 1; i <= n; ++i) {
        for (int j = max(1, i - 1000); j < i; ++j) DS::add(j, get_dis(j, i));
        for (int j = max(1, rev[i] - 1000); j <= min(n,rev[i] + 1000); ++j) {
            int k = ord[j];
            if (k < i) DS::add(k, get_dis(k, i));
        }
        for (auto it : qry[i]) ans[it.second] = DS::query(it.first, i);
    }
    for (int i = 1; i <= q; ++i) cout << ans[i] << "\n";
    return 0;
}