#include <bits/stdc++.h>

#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
using ll = long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;

template<class T>inline void chkmn(T &x, T y) { if (y < x) x = y; }
template<class T>inline void chkmx(T &x, T y) { if (y > x) x = y; }

using namespace std;

const int maxn = 1000010;
const int maxm = maxn * 30;

struct node {
  ll x, y, id;
} a[maxn], b[maxn];

struct info {
  ll l, r, val;
  info() { }
  info(ll x, ll y, ll z) { l = x, r = y, val = z; }
} p[maxn], comb[maxn];

struct atom {
  pii v1, v2;
  int ls, rs;
} t[maxm];

int n, q, pt, c[maxn], pos[maxn], rt[maxn], crt[maxn], tot;
pii rg[maxn];
priority_queue<pair<ll, pii>, vector<pair<ll, pii>>, greater<pair<ll, pii>>> pq;

struct fwt {
  ll t[maxn];
  void init(int n) {
    rep (i, 1, n) t[i] = -1e18;
  }
  void upd(int x, ll v) {
    while (x <= n) {
      if (v < t[x]) return;
      t[x] = v, x += x & (-x);
    }
  }
  void cle(int x) {
    while (x <= n) {
      if (t[x] == -1e18) return;
      t[x] = -1e18, x += x & (-x);
    }
  }
  ll qry(int x) {
    ll res = -1e18;
    while (x) chkmx(res, t[x]), x -= x & (-x);
    return res;
  }
} fwt[2];

ll brute(int l, int r) {
  rep (i, l, r) b[i] = a[i];
  sort(b + l, b + r + 1, [&](node x, node y) { return x.x < y.x; });
  ll res = 1e18;
  rep (i, l, r) {
    chkmn(res, b[i].x + b[i].y - fwt[0].qry(pos[b[i].id]));
    chkmn(res, b[i].x - b[i].y - fwt[1].qry(n - pos[b[i].id] + 1));
    fwt[0].upd(pos[b[i].id], b[i].x + b[i].y);
    fwt[1].upd(n - pos[b[i].id] + 1, b[i].x - b[i].y);
  }
  rep (i, l, r) fwt[0].cle(pos[b[i].id]), fwt[1].cle(n - pos[b[i].id] + 1);
  return res;
}

#define mid ((l + r) >> 1)

void upd(int &p, int q, int l, int r, int x, pii v1, pii v2) {
  p = ++tot, t[p] = t[q];
  if (l == r) return t[p].v1 = v1, t[p].v2 = v2, void();
  if (x <= mid) upd(t[p].ls, t[q].ls, l, mid, x, v1, v2);
  else upd(t[p].rs, t[q].rs, mid + 1, r, x, v1, v2);
  t[p].v1 = max(t[t[p].ls].v1, t[t[p].rs].v1);
  t[p].v2 = max(t[t[p].ls].v2, t[t[p].rs].v2);
}

pii qry1(int p, int l, int r, int x, int y) {
  if (t[p].v1.fi == -2e9 || (l == x && r == y)) return t[p].v1;
  if (y <= mid) return qry1(t[p].ls, l, mid, x, y);
  else if (x > mid) return qry1(t[p].rs, mid + 1, r, x, y);
  else return max(qry1(t[p].ls, l, mid, x, mid), qry1(t[p].rs, mid + 1, r, mid + 1, y));
}

pii qry2(int p, int l, int r, int x, int y) {
  if (t[p].v2.fi == -2e9 || (l == x && r == y)) return t[p].v2;
  if (y <= mid) return qry2(t[p].ls, l, mid, x, y);
  else if (x > mid) return qry2(t[p].rs, mid + 1, r, x, y);
  else return max(qry2(t[p].ls, l, mid, x, mid), qry2(t[p].rs, mid + 1, r, mid + 1, y));
}

int main() {
  cin.tie(nullptr) -> ios::sync_with_stdio(false);
  cin >> n >> q;
  rep (i, 1, n) cin >> a[i].x >> a[i].y, a[i].id = i;
  sort(a + 1, a + n + 1, [&](node x, node y) { return x.y < y.y; });
  rep (i, 1, n) pos[a[i].id] = i;
  sort(a + 1, a + n + 1, [&](node x, node y) { return x.x < y.x; });
  t[0].v1 = t[0].v2 = pii(-2e9, -1);
  rep (i, 1, n) upd(rt[i], rt[i - 1], 1, n, pos[a[i].id], pii(a[i].x + a[i].y, i), pii(a[i].x - a[i].y, i));
  rep (i, 1, n) crt[i] = rt[i - 1];
  rep (i, 1, n) {
    pll w1 = qry1(crt[i], 1, n, 1, pos[a[i].id]), w2 = qry2(crt[i], 1, n, pos[a[i].id], n);
    w1.fi = a[i].x + a[i].y - w1.fi, w2.fi = a[i].x - a[i].y - w2.fi;
    pll cur = min(w1, w2);
    if (cur.se != -1) pq.emplace(cur.fi, pii(i, cur.se));
  }
  rep (i, 1, n / 4) {
    ll val = pq.top().fi;
    auto [x, y] = pq.top().se;
    pq.pop(), p[++pt] = info(min(a[x].id, a[y].id), max(a[x].id, a[y].id), val);
    upd(crt[x], crt[x], 1, n, pos[a[y].id], pii(-2e9, -1), pii(-2e9, -1));
    pll w1 = qry1(crt[x], 1, n, 1, pos[a[x].id]), w2 = qry2(crt[x], 1, n, pos[a[x].id], n);
    w1.fi = a[x].x + a[x].y - w1.fi, w2.fi = a[x].x - a[x].y - w2.fi;
    pll cur = min(w1, w2);
    if (cur.se != -1) pq.emplace(cur.fi, pii(x, cur.se));
  }
  tot = 0;
  rep (i, 1, pt) {
    int ok = 1;
    rep (j, 1, tot) {
      if (comb[j].l >= p[i].l && comb[j].r <= p[i].r) {
        ok = 0; break;
      }
    }
    if (ok) comb[++tot] = p[i];
  }
  sort(a + 1, a + n + 1, [&](node x, node y) { return x.id < y.id; });
  fwt[0].init(n), fwt[1].init(n);
  while (q--) {
    int l, r;
    cin >> l >> r;
    ll ans = 1e18;
    rep (i, 1, tot) {
      if (l <= comb[i].l && comb[i].r <= r) {
        ans = comb[i].val;
        break;
      }
    }
    if (ans == 1e18) ans = brute(l, r);
    cout << ans << '\n';
  }
}