#include <algorithm>
#include <array>
#include <cstddef>
#include <cstdint>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>

namespace {
using std::cin;
using std::cout;
using std::int64_t;
using std::size_t;

namespace base {
template <typename T, size_t... sizes>
struct NestedArray {};

template <typename T, size_t size, size_t... sizes>
struct NestedArray<T, size, sizes...> {
  using Type = std::array<typename NestedArray<T, sizes...>::Type, size>;
};

template <typename T>
struct NestedArray<T> {
  using Type = T;
};

template <typename T, size_t... sizes>
using Array = typename NestedArray<T, sizes...>::Type;

void OptimizeIO() {
  std::ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
}

void OptimizeIO(const std::string &input_file, const std::string &output_file) {
  static std::ifstream input_stream(input_file);
  static std::ofstream output_stream(output_file);
  cin.rdbuf(input_stream.rdbuf()), cout.rdbuf(output_stream.rdbuf());
  cin.tie(nullptr), cout.tie(nullptr);
}
}  // namespace base

using base::Array;

const int kMaxN = 2.5e5 + 5, kMaxLogV = 28;
const int64_t kBase = 1.0e9, kInf = 1.0e18 + 5;
int n, m;
Array<int, kMaxLogV> p;
Array<int64_t, kMaxN> ans;
Array<__gnu_pbds::cc_hash_table<int64_t, std::vector<int>>, kMaxLogV> cell;
__gnu_pbds::cc_hash_table<int64_t, int> vis;

struct Point {
  int x, y;
};

Array<Point, kMaxN> a;

struct Query {
  int l, id;
  Query(int l, int id) : l(l), id(id) {}
};

Array<std::vector<Query>, kMaxN> query;

class Decomposition {
 public:
  void Init(int n) { std::fill_n(a_.begin() + 1, n, kInf); }

  int64_t Query(int l, int r) {
    return *std::min_element(a_.begin() + l, a_.begin() + r + 1);
  }

  void Update(int x, int64_t val) { a_[x] = std::min(a_[x], val); }

 private:
  Array<int64_t, kMaxN> a_;
};

Decomposition decomposition;

inline int64_t Sqr(int x) { return int64_t{x} * x; }

inline int64_t Distance(const Point &a, const Point &b) {
  return Sqr(a.x - b.x) + Sqr(a.y - b.y);
}

void Insert(int i) {
  int &last = vis[kBase * a[i].x + a[i].y];
  if (last) decomposition.Update(last, 0);
  last = i;

  for (int k = 0; k < kMaxLogV; ++k) {
    int x = a[i].x >> (k + 1), y = a[i].y >> (k + 1);
    auto it = cell[k].find(kBase * x + y);

    if (it != cell[k].end()) {
      int q = p[k];

      for (int j : it->second) {
        if (Distance(a[i], a[j]) < (int64_t{1} << (k << 1))) q = std::max(q, j);
      }

      for (int j = p[k] + 1; j <= q; ++j) {
        int x = a[j].x >> (k + 1), y = a[j].y >> (k + 1);
        auto &v = cell[k][x * kBase + y];
        v.erase(std::find(v.begin(), v.end(), j));
      }

      p[k] = q;
    }

    for (int X = x - 1; X <= x + 1; ++X) {
      for (int Y = y - 1; Y <= y + 1; ++Y) {
        it = cell[k].find(kBase * X + Y);

        if (it != cell[k].end()) {
          for (int j : it->second) {
            decomposition.Update(j, Distance(a[i], a[j]));
          }
        }
      }
    }

    cell[k][kBase * x + y].emplace_back(i);
  }
}

int Main() {
  base::OptimizeIO();
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) cin >> a[i].x >> a[i].y;

  for (int i = 1; i <= m; ++i) {
    int l, r;
    cin >> l >> r;
    query[r].emplace_back(l, i);
  }

  decomposition.Init(n);

  for (int i = 1; i <= n; ++i) {
    Insert(i);
    for (const Query &q : query[i]) ans[q.id] = decomposition.Query(q.l, i);
  }

  for (int i = 1; i <= m; ++i) cout << ans[i] << "\n";
  return 0;
}
}  // namespace

int main() { return Main(); }