#ifdef LOCAL
#include "stdafx.h"
#else
#include <bits/stdc++.h>
#define IL inline
#define LL long long
#define eb emplace_back
#define sz(v) ((int) (v).size())
#define me(f, x) memset(f, x, sizeof(f))
#define mc(f, g) memcpy(f, g, sizeof(g))
#define L(i, j, k) for (int i = (j); i <= (k); ++i)
#define R(i, j, k) for (int i = (j); i >= (k); --i)
#define FIO(FILE) freopen(FILE".in", "r", stdin), freopen(FILE".out", "w", stdout)
using namespace std;

using vi = vector<int>;
#endif

namespace IO {
    char ibuf[1 << 20], *iS, *iT, obuf[1 << 20], *oS = obuf;

// Helps
#ifndef LOCAL
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, 1 << 20, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#else
#define gh() getchar()
#endif

	IL void flush () {
		fwrite(obuf, 1, oS - obuf, stdout), oS = obuf;
	}

	struct Flusher {
		~Flusher () {
			flush();
		}
	} AutoFlush;

	IL void pc (char ch) {
		if (oS == obuf + (1 << 20)) flush(); 
		*oS++ = ch;
	}
//

	template<typename T = int>
	IL T rd () {
		char ch = gh();
		T x = 0;
		bool t = 0;
		while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
		while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
		return t ? ~(x - 1) : x;
	}

	char buf[64], *tp = buf;
	template<typename T, enable_if_t<is_signed<T>::value>* = nullptr>
	IL void wr (T x) {
		if (x < 0) {
			x = ~(x - 1);
			pc('-');
		}
		do {
			*tp++ = x % 10;
			x /= 10;
		} while (x);
		while (tp != buf) {
			pc((*--tp) | 48);
		}
	}
	template<typename T, enable_if_t<is_unsigned<T>::value>* = nullptr>
	IL void wr (T x) {
		do {
			*tp++ = x % 10;
			x /= 10;
		} while (x);
		while (tp != buf) {
			pc((*--tp) | 48);
		}
	}

	template<class T>
	IL void wrln (T x) {
		wr(x), pc('\n');
	}
	template<class T>
	IL void wrsp (T x) {
		wr(x), pc(' ');
	}
}

using IO::rd;
using IO::wr;
using IO::wrln;
using IO::wrsp;
using IO::pc;

using pi = pair<int, int>;
#define fi first
#define se second

constexpr int N = 1e6 + 9;
int n, B, Q;

struct P {
  int x, y;
} a[N];

int K;

struct item {
  int x, y;
  LL d;
  bool operator < (const item &rhs) const {
    return d > rhs.d;
  }
} sp[N];

int pa[N], pb[N], rk[N];

namespace init {

int tot, rt[N];

// int f[N << 6], g[N << 6];
// int ls[N << 6], rs[N << 6];

struct nd {
  int x, y, ls, rs;
} t[N << 6];

#define m ((l + r) >> 1)
#define ls(p) t[p].ls
#define rs(p) t[p].rs

IL int cl (int p) {
  t[++tot] = t[p];
  return tot;
}

IL int cpf (int i, int j) {
  return !i || !j ? i | j : a[pb[i]].x + a[pb[i]].y > a[pb[j]].x + a[pb[j]].y ? i : j;
}

IL int cpg (int i, int j) {
  return !i || !j ? i | j : a[pb[i]].x - a[pb[i]].y > a[pb[j]].x - a[pb[j]].y ? i : j;
}

IL void up (int p) {
  t[p].x = cpf(t[ls(p)].x, t[rs(p)].x);
  t[p].y = cpg(t[ls(p)].y, t[rs(p)].y);
}

void ins (int x, int l, int r, int &p) {
  p = cl(p);
  t[p].x = cpf(t[p].x, x);
  t[p].y = cpg(t[p].y, x);
  if (l == r) {
    return;
  }
  x <= m ? ins(x, l, m, ls(p)) : ins(x, m + 1, r, rs(p));
}

void era (int x, int l, int r, int &p) {
  p = cl(p);
  if (l == r) {
    t[p].x = t[p].y = 0;
    return;
  }
  x <= m ? era(x, l, m, ls(p)) : era(x, m + 1, r, rs(p));
  up(p);
}

int qf (int x, int p) {
  int l = 1, r = n, ret = 0;
  while (l < r && p) {
    if (x <= m) {
      r = m;
      p = ls(p);
    } else {
      ret = cpf(ret, t[ls(p)].x);
      l = m + 1;
      p = rs(p);
    }
  }
  return ret;
}

int qg (int x, int p) {
  int l = 1, r = n, ret = 0;
  while (l < r && p) {
    if (m < x) {
      l = m + 1;
      p = rs(p);
    } else {
      ret = cpg(ret, t[rs(p)].y);
      r = m;
      p = ls(p);
    }
  }
  return ret;
}

#undef m

void main () {
  L (i, 1, n) {
    rt[i] = rt[i - 1];
  }
  L (idx, 1, n - 1) {
    int i = pa[idx];
    ins(rk[i], 1, n, rt[idx + 1] = rt[idx]);
  }
  priority_queue<item> q;
  auto get = [&] (int idx) -> item {
    int i = pa[idx];
    int j1 = qf(rk[i], rt[idx]);
    int j2 = qg(rk[i], rt[idx]);
    LL d1 = j1 ? a[i].x + a[i].y - a[pb[j1]].x - a[pb[j1]].y : 1e17;
    LL d2 = j2 ? a[i].x - a[i].y - a[pb[j2]].x + a[pb[j2]].y : 1e17;
    return d1 < d2 ? (item){idx, j1, d1} : (item){idx, j2, d2};
  };
  L (i, 2, n) {
    q.push(get(i));
  }
  B = n / 6;
  L (k, 1, B) {
    auto [x, y, d] = q.top();
    q.pop();
    sp[k] = (item){pa[x], pb[y], d};
    if (sp[k].x > sp[k].y) {
      swap(sp[k].x, sp[k].y);
    }
    era(y, 1, n, rt[x]);
    q.push(get(x));
  }
  int t = 0;
  L (i, 1, B) {
    bool f = true;
    R (j, t, 1) {
      if (sp[i].x <= sp[j].x && sp[j].y <= sp[i].y) {
        f = false;
        break;
      }
    }
    if (f) {
      sp[++t] = sp[i];
    }
  }
  K = t;
}

}

namespace bf {

struct BIT {
  int k;
  LL a[N], b[N];

  void mdya (int x, LL y) {
    for (; x <= k; x += x & -x) {
      a[x] = max(a[x], y);
    }
  }

  LL qrya (int x) {
    LL s = -1e17;
    for (; x; x &= x - 1) {
      s = max(s, a[x]);
    }
    return s;
  }

  void mdyb (int x, LL y) {
    for (; x; x &= x - 1) {
      b[x] = max(b[x], y);
    }
  }

  LL qryb (int x) {
    LL s = -1e17;
    for (; x <= k; x += x & -x) {
      s = max(s, b[x]);
    }
    return s;
  }
} T;

int p[N], q[N];

LL calc (int l, int r) {
  int k = 0;
  L (i, l, r) {
    p[++k] = i;
  }
  sort(p + 1, p + k + 1, [] (int i, int j) {
    return a[i].y < a[j].y;
  });
  L (i, 1, k) {
    q[p[i]] = i;
  }
  sort(p + 1, p + k + 1, [] (int i, int j) {
    return a[i].x < a[j].x;
  });
  T.k = k;
  L (i, 1, k) {
    T.a[i] = T.b[i] = -1e17;
  }
  LL ans = 1e18;
  L (idx, 1, k) {
    int i = p[idx];
    ans = min({ans, a[i].x + a[i].y - T.qrya(q[i]), a[i].x - a[i].y - T.qryb(q[i])});
    T.mdya(q[i], a[i].x + a[i].y);
    T.mdyb(q[i], a[i].x - a[i].y);
  }
  return ans;
}

}

int main () {
  ios::sync_with_stdio(0), cin.tie(0);
  n = rd(), Q = rd();
  L (i, 1, n) {
    a[i].x = rd(), a[i].y = rd();
    pa[i] = i;
    pb[i] = i;
  }
  sort(pa + 1, pa + n + 1, [] (int i, int j) {
    return a[i].x < a[j].x;
  });
  sort(pb + 1, pb + n + 1, [] (int i, int j) {
    return a[i].y < a[j].y;
  });
  L (i, 1, n) {
    rk[pb[i]] = i;
  }
  init::main();
  auto work = [&] (int l, int r) {
    L (i, 1, K) {
      if (l <= sp[i].x && sp[i].y <= r) {
        wrln(sp[i].d);
        return;
      }
    }
    wrln(bf::calc(l, r));
  };
  while (Q--) {
    int l = rd(), r = rd();
    work(l, r);
  }
}
// I love WHQ!