// O(Q sqrt N) solution
#include <bits/stdc++.h>

using namespace std;

namespace {

#define VEVE(i, a, b) for (ll i = a, __##i = b; i < __##i; ++i)
#define RARA(i, a, b) for (ll i = a, __##i = b; i > __##i; --i)
#define VERA(x, seq) for (auto &x : seq)
#define SIZE(x) ((ll)(x.size()))
#define ALL(x) x.begin(), x.end()

typedef int ll;
typedef unsigned long long ull;
typedef double dd;
typedef pair<ll, ll> Pt;
const ll INF = ll(2e9 + 1);

Pt ToPt(ull mask) {
  return Pt(mask >> 32, mask & UINT_MAX);
}

ull ToMask(ll x, ll y) {
  return ull(x) << 32 | y;
}

struct MinMaxSet {
  ull min1, min2, max1, max2;

  MinMaxSet() {
    Clear();
  }

  void Add(ull pt) {
    if (pt < min1) {
      min2 = min1;
      min1 = pt;
    } else if (pt < min2) {
      min2 = pt;
    }
    if (pt > max1) {
      max2 = max1;
      max1 = pt;
    } else if (pt > max2) {
      max2 = pt;
    }
  }

  void Clear() {
    min1 = min2 = ToMask(INF, INF);
    max1 = max2 = ToMask(0, 0);
  }

  void Add(const MinMaxSet& m) {
    Add(m.min1);
    Add(m.min2);
    Add(m.max1);
    Add(m.max2);
  }

  void Sink(vector<Pt>& p) {
    p.push_back(ToPt(min1));
    p.push_back(ToPt(min2));
    p.push_back(ToPt(max1));
    p.push_back(ToPt(max2));
  }
};

struct Block {
  MinMaxSet by_x, by_y;

  void Add(const Pt& pt) {
    by_x.Add(ToMask(pt.first, pt.second));
    by_y.Add(ToMask(pt.second, pt.first));
  }

  void Clear() {
    by_x.Clear();
    by_y.Clear();
  }

  void Add(const Block& b) {
    by_x.Add(b.by_x);
    by_y.Add(b.by_y);
  }
};

const ll MAGIC = 316;

void Solve(ll) {
  ll n, q;
  cin >> n >> q;
  vector<Pt> pts(n);
  VERA(pt, pts) {
    cin >> pt.first >> pt.second;
    pt.first += 1e9 + 1;
    pt.second += 1e9 + 1;
  }
  vector<Block> blocks(n / MAGIC + 1);
  VEVE(i, 0, n) {
    blocks[i / MAGIC].Add(pts[i]);
  }
  Block blo;
  vector<Pt> now;
  VEVE(_, 0, q) {
    ll l, r;
    cin >> l >> r;
    --l, --r;
    blo.Clear();
    {
      ll i = l;
      for (; i % MAGIC and i <= r; ++i)
        blo.Add(pts[i]);
      for (; i + MAGIC - 1 <= r; i += MAGIC)
        blo.Add(blocks[i / MAGIC]);
      for (; i <= r; ++i)
        blo.Add(pts[i]);
    }
    ll res = 2e9;
    now.clear();
    blo.by_x.Sink(now);
    blo.by_y.Sink(now);
    VEVE(i, 4, 8) swap(now[i].first, now[i].second);
    sort(ALL(now));
    now.erase(unique(ALL(now)), now.end());
    while (now.front().first == 0)
      now.erase(now.begin());
    while (now.back().first == INF)
      now.erase(--now.end());
    assert(2 <= SIZE(now) and SIZE(now) <= 8);
    VEVE(del, 0, SIZE(now)) {
      ll min_x = INF, min_y = INF, max_x = 0, max_y = 0;
      VEVE(i, 0, SIZE(now)) {
        if (i != del) {
          min_x = min(min_x, now[i].first);
          max_x = max(max_x, now[i].first);
          min_y = min(min_y, now[i].second);
          max_y = max(max_y, now[i].second);
        }
      }
      res = min(res, max(max_x - min_x, max_y - min_y));
    }
    cout << res << '\n';
  }
}

void Init() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
}

}

int main() {
#ifdef AZN
  freopen("input.txt", "r", stdin);
#endif
  Init();
  ll tests = 1;
  VEVE(test, 1, tests + 1) Solve(test);
  return 0;
}