#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
         << ": ";                                          \
    dbgh(__VA_ARGS__)
#else
#define cerr   \
    if (false) \
    cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

constexpr int logn = 30;

long sq(long x) {
    return x * x;
}

struct chash {
    static uint64_t hash(uint64_t x) {
        x ^= x >> 33;
        x ^= x >> 17;
        x ^= x << 25;
        x ^= x >> 22;
        return x;
    }

    uint64_t operator()(uint64_t x) const {
        return hash(x);
    }
};

struct HT {
    static constexpr int maxn = 1 << 20;

    long ks[maxn];
    basic_string<int> vs[maxn];

    HT() {
        memset(ks, -1, sizeof(ks));
    }

    int b_find(long x) {
        for (int i = int(chash::hash(x) & (maxn - 1));; i++, i &= (maxn - 1)) {
            if (ks[i] == -1 || ks[i] == x) {
                return i;
            }
        }
    }

    optional<basic_string<int>*> find(long x) {
        int ind = b_find(x);
        if (ks[ind] == -1) {
            return {};
        }
        return &vs[ind];
    }

    basic_string<int>& operator[](long x) {
        int ind = b_find(x);
        ks[ind] = x;
        return vs[ind];
    }
} mps[logn];

template <typename T>
optional<basic_string<int>*> find(T& h, long x) {
    auto it = h.find(x);
    if (it == h.end()) {
        return {};
    }
    return &it->second;
}

template <>
optional<basic_string<int>*> find(HT& h, long x) {
    return h.find(x);
}

struct DS1 {
    int n;
    vector<long> v;

    DS1(int n) : n(n), v(n + 1, 1e18) {}

    void update(int ind, long x) {
        ind++;
        while (ind <= n) {
            v[ind] = min(v[ind], x);
            ind += ind & -ind;
        }
    }

    long query(int ind) const {
        ind++;
        long ans = 1e18;
        while (ind > 0) {
            ans = min(ans, v[ind]);
            ind -= ind & -ind;
        }
        return ans;
    }
};

void solve() {
    int n, q;
    cin >> n >> q;
    int arr[n][2];
    for (auto& [x, y] : arr) {
        cin >> x >> y;
    }
    long qans[q], cans[n];
    memset(cans, 0x3f, sizeof(cans));
    vector<pair<int, int>> queries[n];
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        l--;
        r--;
        queries[l].emplace_back(r, i);
    }
    auto dist = [&](int u, int v) -> long {
        return sq(arr[u][0] - arr[v][0]) + sq(arr[u][1] - arr[v][1]);
    };
    auto hsh = [&](int x, int y) -> long { return (long(x) << 32) | y; };
    DS1 ds1(n);
//    map<long, basic_string<int>> mps[logn];
//    __gnu_pbds::gp_hash_table<long, basic_string<int>, chash> mps[logn];
    for (int i = n - 1; i >= 0; i--) {
        auto& [x, y] = arr[i];
        for (int j = 0; j < logn; j++) {
            int bx = x >> j, by = y >> j;
            for (int dx : {-1, 0, 1}) {
                for (int dy : {-1, 0, 1}) {
                    auto it = find(mps[j], hsh(bx + dx, by + dy));
                    if (!it) {
                        continue;
                    }
                    auto &cv = *it.value();
                    basic_string<int> nxt;
                    for (auto& a : cv) {
                        long cdist = dist(i, a);
                        if (cdist < cans[a]) {
                            cans[a] = cdist;
                            ds1.update(a, cdist);
                        }
                        if (cdist >= sq(1 << j)) {
                            nxt.push_back(a);
                        }
                    }
                    assert(sz(nxt) <= 100);
                    cv = std::move(nxt);
                }
            }
            mps[j][hsh(bx, by)].push_back(i);
        }
        for (auto& [qr, qi] : queries[i]) {
            qans[qi] = ds1.query(qr);
        }
    }
    for (auto& a : qans) {
        cout << a << endl;
    }
}

int main() {
    cin.tie(nullptr);
    cin.exceptions(ios::failbit);
    ios_base::sync_with_stdio(false);
    solve();
}