#include<bits/stdc++.h>

using namespace std;
const int N = 2e5 + 7;
const int inf = 0x3f3f3f3f;
int n, q;
int x[N], y[N];
vector<int> v;
vector<pair<int, int>> px[N], py[N];

struct info {
    int mnx, mxx, mny, mxy;

    info(int nx = inf, int xx = -inf, int ny = inf, int xy = -inf) {
        mnx = nx;
        mxx = xx;
        mny = ny;
        mxy = xy;
    }

    int get() {
        return max(mxx - mnx, mxy - mny);
    }
};

info operator+(const info &o1, const info &o2) {
    info ans;
    ans.mnx = min(o1.mnx, o2.mnx);
    ans.mxx = max(o1.mxx, o2.mxx);
    ans.mny = min(o1.mny, o2.mny);
    ans.mxy = max(o1.mxy, o2.mxy);
    return ans;
}

struct node {
    int l, r;
    info v;
} Tree[N << 2];

void build(int k, int l, int r) {
    Tree[k].l = l;
    Tree[k].r = r;
    if (l == r) {
        Tree[k].v = info(x[l], x[l], y[l], y[l]);
        return;
    }
    int mid = (l + r) >> 1;
    build(k << 1, l, mid);
    build(k << 1 | 1, mid + 1, r);
    Tree[k].v = Tree[k << 1].v + Tree[k << 1 | 1].v;
}

info query(int k, int l, int r) {
    if (l > r)return info();
    if (Tree[k].l >= l && Tree[k].r <= r)return Tree[k].v;
    int mid = (Tree[k].l + Tree[k].r) >> 1;
    if (r <= mid)return query(k << 1, l, r);
    if (l > mid)return query(k << 1 | 1, l, r);
    return query(k << 1, l, r) + query(k << 1 | 1, l, r);
}

int get(int x) {
    return lower_bound(v.begin(), v.end(), x) - v.begin();
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
        v.push_back(x[i]);
        v.push_back(y[i]);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    int siz = v.size();
    for (int i = 1; i <= n; i++) {
        px[get(x[i])].push_back({y[i], i});
        py[get(y[i])].push_back({x[i], i});
    }
    for (int i = 0; i < siz; i++) {
        sort(px[i].begin(), px[i].end());
        sort(py[i].begin(), py[i].end());
    }
    build(1, 1, n);
    while (q--) {
        int l, r;
        cin >> l >> r;
        info res = query(1, l, r);
        int ans = res.get();
        int id = get(res.mnx);
        int pos = lower_bound(px[id].begin(), px[id].end(), make_pair(res.mny, -inf))->second;
        info now = query(1, l, pos - 1) + query(1, pos + 1, r);
        ans = min(ans, now.get());
        id = get(res.mxx);
        pos = lower_bound(px[id].begin(), px[id].end(), make_pair(res.mny, -inf))->second;
        now = query(1, l, pos - 1) + query(1, pos + 1, r);
        ans = min(ans, now.get());
        id = get(res.mny);
        pos = lower_bound(py[id].begin(), py[id].end(), make_pair(res.mnx, -inf))->second;
        now = query(1, l, pos - 1) + query(1, pos + 1, r);
        ans = min(ans, now.get());
        id = get(res.mxy);
        pos = lower_bound(py[id].begin(), py[id].end(), make_pair(res.mnx, -inf))->second;
        now = query(1, l, pos - 1) + query(1, pos + 1, r);
        ans = min(ans, now.get());
        cout << ans << "\n";
    }
    return 0;
}