#include <bits/stdc++.h>
#define MAXN 1000010
using namespace std;

int n, q, k, tot;
long long x[MAXN], y[MAXN];
long long bit[MAXN];
int idx[MAXN], idy[MAXN], rkx[MAXN], rky[MAXN];
long long b[MAXN];
pair<int, int> a[MAXN];
const long long inf = 1e10;

long long Getdis(int i, int j) {
	return abs(x[i] - x[j]) + abs(y[i] - y[j]);
}

int max1(int i, int j) {return x[i] + y[i] > x[j] + y[j] ? i : j;}
int max2(int i, int j) {return x[i] - y[i] > x[j] - y[j] ? i : j;}

bool cmpx(int i, int j) {return x[i] < x[j];}
bool cmpy(int i, int j) {return y[i] < y[j];}

void BIT_Insert(int p, long long val) {
	while (p <= n) bit[p] = max(bit[p], val), p += p & -p;
	return;
}

long long BIT_Query(int p) {
	long long ans = -inf;
	while (p) ans = max(ans, bit[p]), p -= p & -p;
	return ans;
}

long long BF_Solve(int l, int r) {
	long long ans = inf;
	for (int i = 1; i <= n; ++i) bit[i] = -inf;
	for (int i = 1; i <= n; ++i) {
		int p = idx[i];
		if (p < l || p > r) continue;
		ans = min(ans, x[p] + y[p] - BIT_Query(rky[p]));
		BIT_Insert(rky[p], x[p] + y[p]);
	}
	for (int i = 1; i <= n; ++i) bit[i] = -inf;
	for (int i = 1; i <= n; ++i) {
		int p = idx[i];
		if (p < l || p > r) continue;
		ans = min(ans, x[p] - y[p] - BIT_Query(n - rky[p] + 1));
		BIT_Insert(n - rky[p] + 1, x[p] - y[p]);
	}
	return ans;
}

struct SegTree{
	int l, r, lson, rson;
	int v1, v2;
}tree[MAXN * 24];

int stot;

void Build(const int p, const int l, const int r) {
	tree[p].l = l, tree[p].r = r;
	if (l == r) return;
	int mid = (l + r) >> 1;
	Build(tree[p].lson = ++stot, l, mid);
	Build(tree[p].rson = ++stot, mid + 1, r);
	return;
}

void Modify(const int p, const int q, const int pos) {
	if (tree[p].l == tree[p].r) {tree[p].v1 = tree[p].v2 = idy[pos]; return;}
	int mid = (tree[p].l + tree[p].r) >> 1;
	if (pos <= mid) {
		tree[p].lson = ++stot;
		tree[stot] = SegTree{tree[p].l, mid};
		tree[p].rson = tree[q].rson;
		Modify(tree[p].lson, tree[q].lson, pos);
	}
	else {
		tree[p].rson = ++stot;
		tree[stot] = SegTree{mid + 1, tree[p].r};
		tree[p].lson = tree[q].lson;
		Modify(tree[p].rson, tree[q].rson, pos);
	}
	tree[p].v1 = max1(tree[tree[p].lson].v1, tree[tree[p].rson].v1);
	tree[p].v2 = max2(tree[tree[p].lson].v2, tree[tree[p].rson].v2);
	return;
}

int Query1(const int p, const int l, const int r) {
	if (tree[p].l >= l && tree[p].r <= r) return tree[p].v1;
	int mid = (tree[p].l + tree[p].r) >> 1;
	if (l <= mid) {
		if (mid < r) return max1(Query1(tree[p].lson, l, r), Query1(tree[p].rson, l, r));
		return Query1(tree[p].lson, l, r);
	}
	return Query1(tree[p].rson, l, r);
}

int Query2(const int p, const int l, const int r) {
	if (tree[p].l >= l && tree[p].r <= r) return tree[p].v2;
	int mid = (tree[p].l + tree[p].r) >> 1;
	if (l <= mid) {
		if (mid < r) return max2(Query2(tree[p].lson, l, r), Query2(tree[p].rson, l, r));
		return Query2(tree[p].lson, l, r);
	}
	return Query2(tree[p].rson, l, r);
}

struct Node{
	long long val;
	int p1, p2, l, r, op;
};
bool operator<(Node a, Node b) {return a.val > b.val;}
priority_queue<Node> qu;

void Split1(Node now) {
	int p1 = now.p1, p2 = now.p2, l = now.l, r = now.r;
	int mid = rky[p2];
	if (l < mid) {
		int ql = Query1(rkx[p1] - 1, l, mid - 1);
		qu.push(Node{Getdis(p1, ql), p1, ql, l, mid - 1, 1});
	}
	if (mid < r) {
		int qr = Query1(rkx[p1] - 1, mid + 1, r);
		qu.push(Node{Getdis(p1, qr), p1, qr, mid + 1, r, 1});
	}
	return;
}

void Split2(Node now) {
	int p1 = now.p1, p2 = now.p2, l = now.l, r = now.r;
	int mid = rky[p2];
	if (l < mid) {
		int ql = Query2(rkx[p1] - 1, l, mid - 1);
		qu.push(Node{Getdis(p1, ql), p1, ql, l, mid - 1, 2});
	}
	if (mid < r) {
		int qr = Query2(rkx[p1] - 1, mid + 1, r);
		qu.push(Node{Getdis(p1, qr), p1, qr, mid + 1, r, 2});
	}
	return;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> q; k = n;
	for (int i = 1; i <= n; ++i) cin >> x[i] >> y[i], idx[i] = idy[i] = i;
	sort(idx + 1, idx + n + 1, cmpx);
	sort(idy + 1, idy + n + 1, cmpy);
	for (int i = 1; i <= n; ++i) rkx[idx[i]] = i, rky[idy[i]] = i;
	stot = n, x[0] = -inf;
	for (int i = 1; i <= n; ++i) tree[i] = SegTree{1, n};
	Build(0, 1, n);
	for (int i = 1; i <= n; ++i) {
		int p = idx[i];
		Modify(i, i - 1, rky[p]);
	}
	for (int i = 1; i <= n; ++i) {
		int p = idx[i];
		int q1 = Query1(i - 1, 1, rky[p]);
		qu.push(Node{Getdis(p, q1), p, q1, 1, rky[p], 1});
		int q2 = Query2(i - 1, rky[p], n);
		qu.push(Node{Getdis(p, q2), p, q2, rky[p], n, 2});
	}
	for (int i = 1; i <= k; ++i) {
		Node now = qu.top(); qu.pop();
		a[i] = make_pair(now.p1, now.p2);
		if (now.op == 1) Split1(now);
		else Split2(now);
	}
	for (int i = 1; i <= k; ++i) {
		bool flag = 1;
		if (a[i].first > a[i].second) swap(a[i].first, a[i].second);
		for (int j = 1; j <= tot; ++j) if (a[i].first <= a[j].first && a[i].second >= a[j].second) {flag = 0; break;}
		if (flag) a[++tot] = a[i];
	}
	while (q--) {
		int l, r;
		cin >> l >> r;
		bool flag = 1;
		for (int i = 1; i <= tot; ++i) if (a[i].first >= l && a[i].second <= r) {
			cout << Getdis(a[i].first, a[i].second) << "\n";
			flag = 0;
			break;
		}
		if (flag) cout << BF_Solve(l, r) << "\n";
	}
	return 0;
}