#include <bits/stdc++.h>
using namespace std;
const int INF = 2 * (int)1e9 + 7;

struct Seg {
	private:
		const array<int, 3> neutral = {-INF, -INF, -1};
		vector<array<int, 3>> maxs;
		int h = 1;

		array<int, 3> combine(const array<int, 3>& a, const array<int, 3>& b) {
			auto res = neutral;
			if (a[0] > b[0]) {
				res[0] = a[0];
				res[1] = max(a[1], b[0]);
				res[2] = a[2];
			} else {
				res[0] = b[0];
				res[1] = max(a[0], b[1]);
				res[2] = b[2];
			}
			return res;
		}

		array<int, 3> recGet(int a, int b, int i, int ia, int ib) {
			if (ib <= a || b <= ia) return neutral;
			if (a <= ia && ib <= b) return maxs[i];

			int im = (ia + ib) >> 1;
			return combine(recGet(a, b, 2*i, ia, im), recGet(a, b, 2*i+1, im, ib));
		}
	public:
		Seg(const vector<int>& vec) {
			int n = vec.size();
			while(h < n) h <<= 1;

			maxs.resize(2*h, neutral);
			for (int i = 0; i < n; ++i) {
				maxs[i + h][0] = vec[i];
				maxs[i + h][2] = i;
			}
			for (int i = h-1; i > 0; --i) maxs[i] = combine(maxs[2*i], maxs[2*i+1]);
		}
		array<int, 3> get(int a, int b) {
			return recGet(a, b + 1, 1, 0, h);
		}

};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n, q;
	cin >> n >> q;

	vector<int> xs(n), ys(n), rxs(n), rys(n);
	for (int i = 0; i < n; ++i) {
		cin >> xs[i] >> ys[i];
		rxs[i] = -xs[i];
		rys[i] = -ys[i];
	}
	
	Seg x0(rxs), x1(xs), y0(rys), y1(ys);
	for (int qi = 0; qi < q; ++qi) {
		int a, b;
		cin >> a >> b;
		--a; --b;

		auto lo_x = x0.get(a, b);
		auto hi_x = x1.get(a, b);
		auto lo_y = y0.get(a, b);
		auto hi_y = y1.get(a, b);
		lo_x[0] *= -1;
		lo_y[0] *= -1;
		lo_x[1] *= -1;
		lo_y[1] *= -1;

		vector<int> inds = {lo_x[2], hi_x[2], lo_y[2], hi_y[2]};

		int res = INF;
		for (int ind : inds) {
			int dx = hi_x[ind == hi_x[2]] - lo_x[ind == lo_x[2]];
			int dy = hi_y[ind == hi_y[2]] - lo_y[ind == lo_y[2]];
			res = min(res, max(dx, dy));
		}
		cout << res << '\n';
	}
}