#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const ll inf = 0x3f3f3f3f3f3f3f3f;

const int N = 2.5e5;
const int B = 500;
const int LG = 28;
const int D = 3;

int n, q;

struct SqrtDecomposition {
  int pos[N + 5];
  ll val[N + 5], sum[B + 5];
  void init(int n) {
    for (int i = 1; i <= n; ++i) pos[i] = (i - 1) / B + 1;
    fill_n(val + 1, n, inf), fill_n(sum + 1, pos[n], inf);
  }
  void insert(int x, ll k) {
    val[x] = min(val[x], k), sum[pos[x]] = min(sum[pos[x]], k);
  }
  ll query(int x) {
    ll ret = inf;
    for (int i = x; i <= min(pos[x] * B, n); ++i) ret = min(ret, val[i]);
    for (int p = pos[x] + 1; p <= pos[n]; ++p) ret = min(ret, sum[p]);
    return ret;
  }
} sd;

int x[N + 5], y[N + 5];
ll dist(ll i, ll j) { return (ll)(x[i] - x[j]) * (x[i] - x[j]) + (ll)(y[i] - y[j]) * (y[i] - y[j]); }
ll id(int x, int y) { return (ll)x << 30 | y; }
unordered_map<ll, pair<int, int>> pos;
int a[N + 5];
vector<int> upd[N + 5];
vector<pair<int, int>> qry[N + 5];
ll ans[N + 5];

int main() {
  scanf("%d%d", &n, &q);
  for (int i = 1; i <= n; ++i) scanf("%d%d", x + i, y + i), a[i] = i;
  for (int k = 0; k < LG; ++k) {
    sort(a + 1, a + n + 1, [&](int i, int j) {
      return id(x[i] >> k, y[i] >> k) < id(x[j] >> k, y[j] << k);
    });
    for (int l = 1, r; l <= n; l = r + 1) {
      ll cur = id(x[a[l]] >> k, y[a[l]] >> k);
      for (r = l; r < n && id(x[a[r + 1]] >> k, y[a[r + 1]] >> k) == cur; ++r);
      sort(a + l, a + r + 1), pos[cur] = {l, r};
      for (int i = l; i < r; ++i)
        for (int j = i + 1; j <= i + D && j <= r; ++j)
          upd[a[j]].push_back(a[i]);
    }
    for (int l = 1, r; l <= n; l = r + 1) {
      ll cur = id(x[a[l]] >> k, y[a[l]] >> k);
      tie(l, r) = pos[cur];
      for (auto [dx, dy] : vector<pair<int, int>>{{-1, 1}, {0, 1}, {1, 1}, {1, 0}}) {
        if (dx == -1 && !(x[a[l]] >> k)) continue;
        ll d = cur + id(dx, dy);
        if (!pos.count(d)) continue;
        auto [dl, dr] = pos[d];
        if (l > r || dl > dr) {
          puts("FUCK"); return 0;
        }
        vector<int> vec(a + l, a + r + 1);
        vec.insert(vec.end(), a + dl, a + dr + 1);
        inplace_merge(vec.begin(), vec.begin() + r - l + 1, vec.end());
        for (int i = 0; i < vec.size(); ++i)
          for (int j = i + 1; j <= i + D && j < vec.size(); ++j)
            upd[vec[j]].push_back(vec[i]);
      }
    }
    unordered_map<ll, pair<int, int>>().swap(pos);
  }
  for (int i = 1; i <= q; ++i) {
    int l, r; scanf("%d%d", &l, &r), qry[r].emplace_back(l, i);
  }
  sd.init(n);
  for (int i = 1; i <= n; ++i) {
    for (int j : upd[i]) sd.insert(j, dist(i, j));
    for (auto [l, id] : qry[i]) ans[id] = sd.query(l);
  }
  for (int i = 1; i <= q; ++i) printf("%lld\n", ans[i]);
}