#include <bits/stdc++.h>
#define File(name) freopen(#name".in", "r", stdin); freopen(#name".out", "w", stdout);
using namespace std;
using ll = long long;
using ull = unsigned long long;
template<typename T>
inline T read(){
    T n = 0; int f = 1; char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(isdigit(ch)){
        n = n * 10 + ch - '0';
        ch = getchar();
    }
    return f * n;
}
template<typename T>
void write(T n){
    if(n < 0) return putchar('-'), write(-n);
    if(n / 10) write(n / 10);
    putchar(n % 10 + '0');
}
void input() {}
template<typename Type, typename... Types>
void input(Type &arg, Types &...args){
    arg = read<Type>();
    input(args...);
}
namespace Main{
    const int N = 250005;
    const int B = 505;
    int n, q, x[N], y[N], len, blocks, L[B], R[B], bel[N];
    ll val[N], mn[B], ans[N];
    vector<pair<int, int>> buc[N];
    unordered_set<int> s[N];
    mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
    struct hash{
        ll operator () (const pair<int, int> a) const { return 1ll * a.first * N + a.second; }
    };
    template<typename T>
    inline T min(T a, T b) { return a < b ? a : b; }
    inline ll sqr(ll val) { return val * val; }
    inline ll dis_sqr(int i, int j) { return sqr(x[i] - x[j]) + sqr(y[i] - y[j]); }
    void add(int a, int b){
        if(a > b) swap(a, b);
        s[b].insert(a);
    }
    void Main(){
        input(n, q);
        uniform_int_distribution<int> gen(0, 1e8);
        int x0 = gen(rnd), y0 = gen(rnd);
        for(int i = 1; i <= n; i++){
            input(x[i], y[i]);
            x[i] += x0, y[i] += y0;
        }
        for(int i = 0; i < 28; i++){
            vector<int> ord(n);
            iota(ord.begin(), ord.end(), 1);
            stable_sort(ord.begin(), ord.end(), [&](int a, int b){
                return x[a] >> i == x[b] >> i ? y[a] >> i < y[b] >> i : x[a] >> i < y[a] >> i;
            });
            unordered_map<pair<int, int>, pair<int, int>, hash> mp;
            for(int l = 0, r = 0; l < n; l = r){
                r = l;
                while(r < n && x[ord[r]] >> i == x[ord[l]] >> i && y[ord[r]] >> i == y[ord[l]] >> i) r++;
                mp[{x[ord[l]] >> i, y[ord[l]] >> i}] = {l, r};
                for(int j = l; j < r; j++){
                    for(int k = j + 1; k < j + 10 && k < r; k++){
                        add(ord[j], ord[k]);
                    }
                }
                assert(is_sorted(ord.begin() + l, ord.begin() + r));
            }
            static const vector<pair<int, int>> mv = {{1, -1}, {1, 0}, {1, 1}, {0, -1}};
            for(auto [key, val]: mp) for(auto [dx, dy]: mv){
                if(mp.count({key.first + dx, key.second + dy})){
                    pair<int, int> &v2 = mp[{key.first + dx, key.second + dy}];
                    vector<int> vec(val.second - val.first + v2.second - v2.first);
                    merge(
                        ord.begin() + val.first, ord.begin() + val.second,
                        ord.begin() + v2.first, ord.begin() + v2.second,
                        vec.begin()
                    );
                    for(int j = 0; j < vec.size(); j++){
                        for(int k = j + 1; k < j + 10 && k < vec.size(); k++){
                            add(vec[j], vec[k]);
                        }
                    }
                }
            }
        }
        memset(val, 0x3f, sizeof(val)), memset(mn, 0x3f, sizeof(mn));
        len = sqrt(n), blocks = (n - 1) / len + 1;
        for(int i = 0; i < blocks; i++){
            L[i] = i * len + 1;
            R[i] = min((i + 1) * len, n);
            for(int j = L[i]; j <= R[i]; j++) bel[j] = i;
        }
        auto query = [&](int l, int r){
            ll res = 1e18;
            if(bel[l] == bel[r]) for(int i = l; i <= r; i++) res = min(res, val[i]);
            else{
                for(int i = l; i <= R[bel[l]]; i++) res = min(res, val[i]);
                for(int i = L[bel[r]]; i <= r; i++) res = min(res, val[i]);
                for(int i = bel[l] + 1; i < bel[r]; i++) res = min(res, mn[i]);
            }
            return res;
        };
        for(int i = 0, l, r; i < q; i++){
            input(l, r);
            buc[r].emplace_back(l, i);
        }
        for(int i = 1; i <= n; i++){
            for(int p: s[i]){
                ll d = dis_sqr(p, i);
                val[p] = min(val[p], d);
                mn[bel[p]] = min(mn[bel[p]], d);
            }
            for(auto [l, id]: buc[i]){
                ans[id] = query(l, i);
            }
        }
        for(int i = 0; i < q; i++) write(ans[i]), puts("");
        return;
    }
} // namespace Main
int main(){
#ifdef Liuxizai
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif // Liuxizai
    Main::Main();
    return 0;
}