#include <bits/stdc++.h>
#define fs first
#define sc second
#define pb push_back
#define LOG(FMT...) fprintf(stderr, FMT);
#define rep(i, j, k) for(int i = j; i <= k; ++ i)
#define per(i, j, k) for(int i = j; i >= k; -- i)
using namespace std;
using pii = pair<int, int>;
using ll = long long;
const int N = 3e5 + 5;
const ll INF = 1e18;
pii a[N];
int n, q, mx[N];
ll ans[N], bit[N];
vector<pii> vec[N];
map< pii, vector<int> > sys[32];
ll pw(ll x) { return x * x; }
ll dis(int x, int y) {
  return pw(a[x].fs - a[y].fs) + pw(a[x].sc - a[y].sc);
}
void init() {
  rep(i, 1, n) bit[i] = INF;
}
void ins(int x, ll y) {
  x = n-x+1;
  for(; x <= n; x += x & (-x))
    bit[x] = min(bit[x], y);
}
ll qry(int x) {
  x = n-x+1;
  ll ans = INF;
  for(; x >= 1; x &= x-1)
    ans = min(ans, bit[x]);
  return ans;
}
int main() {
  scanf("%d%d", &n, &q);
  rep(i, 1, n) {
    scanf("%d%d", &a[i].fs, &a[i].sc);
  }
  rep(i, 1, q) {
    int l, r;
    scanf("%d%d", &l, &r);
    vec[r].pb(pii(l, i));
  }
  init();
  rep(r, 1, n) {
    int cur = 0;
    rep(k, 0, 26) {
      int x = a[r].fs >> (k+1), y = a[r].sc >> (k+1);
      int _mx = 0;
      rep(dx, -1, 1) rep(dy, -1, 1) {
        auto &it = sys[k][pii(x+dx, y+dy)];
        while(it.size() && *it.begin() <= cur)
          it.erase(it.begin());
        for(int z: it) {
          ll t = dis(z, r);
          if(t < (1ll << (2*k))) {
            ins(z, t);
            mx[k] = max(mx[k], z);
          }
        }
      }
      cur = max(cur, mx[k]);
      auto &it = sys[k][pii(x, y)];
      for(int &z: it)
        if(a[z] == a[r]) {
          it.erase(lower_bound(it.begin(), it.end(), z));
          break;
        }
      it.pb(r);
    }
    for(auto it: vec[r])
      ans[it.sc] = qry(it.fs);
  }
  rep(i, 1, q)
    printf("%lld\n", ans[i]);
  return 0;
}