#include <bits/stdc++.h>
#include <bits/extc++.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, B = 1e9;
pii a[N];
int n, q, mx[N];
ll ans[N], bit[N];
vector<pii> vec[N];
__gnu_pbds::gp_hash_table< ll, vector<int> > sys[28];
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, 27) {
      int x = a[r].fs >> (k+1), y = a[r].sc >> (k+1);
      rep(dx, -1, 1) rep(dy, -1, 1) if(sys[k].count((x+dx)*B+ y+dy)) {
        auto &it = sys[k][(x+dx)*B+ y+dy];
        auto bg = it.begin();
        while(bg != it.end() && *bg <= cur)
          ++bg;
        it.erase(it.begin(), bg);
        for(int z: it) {
          ll t = dis(z, r);
          if(t < (1ll << (2*(k+1)))) {
            ins(z, t);
            mx[k] = max(mx[k], z);
          }
        }
      }
      cur = max(cur, mx[k]);
      auto &it = sys[k][x*B + 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;
}

answer.code: In function ‘int main()’:
answer.code:52:47: error: ‘class __gnu_pbds::gp_hash_table<long long int, std::vector<int> >’ has no member named ‘count’
   52 |       rep(dx, -1, 1) rep(dy, -1, 1) if(sys[k].count((x+dx)*B+ y+dy)) {
      |                                               ^~~~~
answer.code:39:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   39 |   scanf("%d%d", &n, &q);
      |   ~~~~~^~~~~~~~~~~~~~~~
answer.code:41:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   41 |     scanf("%d%d", &a[i].fs, &a[i].sc);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
answer.code:44:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   44 |     scanf("%d%d", &l, &r);
      |     ~~~~~^~~~~~~~~~~~~~~~