#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define R(i, x, y) for (int i = (x); i >= (y); i--)
#define FIO(FILE) freopen(FILE".in", "r", stdin), freopen(FILE".out", "w", stdout)

using namespace std;
typedef long long ll;
typedef pair<ll, int> pi;
bool Mbe;

// #define LOCAL
#define IL inline

namespace IO {
    char ibuf[1 << 20], *iS, *iT, obuf[1 << 20], *oS = obuf;
#define wrsp(x) wr(x), pc(' ')
#define wrln(x) wr(x), pc('\n')

// 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 = ll>
	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);
		}
	}
}

using IO::rd;
using IO::wr;
using IO::pc;

const int N = 1e6 + 5;
const ll inf = 1e18;

int n, m;
int a[N], b[N];

ll ans[N];

struct Q {
	
	int l, r, i;
	
	Q () { }
	Q (int _l, int _r, int _i) : l(_l), r(_r), i(_i) { }
	
};

vector<Q> q;

ll Abs(ll x) {
	if (x >= 0) {
		return x;
	} else {
		return -x;
	}
}

void conq(vector<Q> qs, vector<int> qi) {
	if (qs.empty()) {
		return;
	}
	int l = n + 1, r = 0;
	for (Q i : qs) {
		l = min(l, i.l);
		r = max(r, i.r);
	}
	vector<int> id;
	for (int i : qi) {
		if (i >= l && i <= r) {
			id.eb(i);
		}
	}
	int p, q;
	ll res = inf;
	p = q = -1;
	F (_, l, r) {
		int i = id[_ - l];
		F (__, max(l, _ - 10), _ - 1) {
			int j = id[__ - l];
			ll tres = Abs(a[i] - a[j]) + Abs(b[i] - b[j]);
			if (res > tres) {
				res = tres;
				p = i, q = j;
			}
		}
	}
	if (p > q) {
		swap(p, q);
	}
	vector<Q> ql, qr;
	for (Q i : qs) {
		if (i.l <= p && i.r >= q) {
			ans[i.i] = res;
		} else if (i.r < q) {
			ql.eb(i);
		} else {
			qr.eb(i);
		}
	}
	if (!ql.empty()) {
		conq(ql, id);
	}
	if (!qr.empty()) {
		conq(qr, id);
	}
}

void solve() {
	n = rd(), m = rd();
	F (i, 1, n) {
		a[i] = rd(), b[i] = rd();
	}
	F (i, 1, m) {
		int l, r;
		l = rd(), r = rd();
		q.eb(Q(l, r, i));
	}
	vector<int> id;
	F (i, 1, n) {
		id.eb(i);
	}
	sort(id.begin(), id.end(), [](int &x, int &y) {
		return a[x] == a[y] ? b[x] < b[y] : a[x] < a[y];
	});
	conq(q, id);
	F (i, 1, m) {
		wr(ans[i]), pc('\n');
	}
}

bool Med;
int main() {
	// FIO("");
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cerr << (&Mbe - &Med) / 1048576.0 << " MB\n";
	int T = 1;
	// cin >> T;
	while (T--) solve();
	cerr << (int)(1e3 * clock() / CLOCKS_PER_SEC) << " ms\n";
	return 0;
}