#include <algorithm>
#include <cassert>
#include <cstdio>
#include <deque>
#include <random>
using namespace std;
mt19937 rng(random_device{}());
int read() {
    char c = getchar();
    int x = 0;
    bool f = 0;
    while (c < 48 or c > 57)
        f |= (c == '-'), c = getchar();
    do
        x = (x * 10) + (c ^ 48), c = getchar();
    while (c >= 48 and c <= 57);
    return f ? -x : x;
}
typedef long long ll;
const int N = 1000003;
const int INF = 0x3f3f3f3f;
const ll lINF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int, int> pii;
int n, m;
int ps[N];
ll res[N], lim;
int tr[N];
int px[N], py[N];
struct node {
    int x, y, id;
    friend bool operator<(const node a, const node b) {
        return a.x < b.x;
    }
} s[N];
vector<pii> vec[N], vq[N];
inline void chmn(int &x, int v) {
    if (x > v)
        x = v;
}
inline void chmn(ll &x, ll v) {
    if (x > v)
        x = v;
}
inline void chmx(int &x, int v) {
    if (x < v)
        x = v;
}
void upd(int x, int v) {
    while (x) {
        chmn(tr[x], v);
        x ^= (x & -x);
    }
}
int qry(int x) {
    int res = INF;
    while (x <= n) {
        chmn(res, tr[x]);
        x += (x & -x);
    }
    return res;
}
int main() {
    n = read(), m = read();
    for (int i = 1; i <= n; ++i)
        px[i] = s[i].x = read(), py[i] = s[i].y = read(), s[i].id = i;
    sort(s + 1, s + n + 1);
    lim = lINF;
    for (int i = 1; 2 * i <= n; ++i) {
        int u = rng() % n + 1;
        int v = rng() % n + 1;
        if (u == v)
            continue;
        chmn(lim, (ll)abs(s[u].x - s[v].x) + (ll)abs(s[u].y - s[v].y));
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            if (s[j].x - s[i].x > lim)
                break;
            ll dis = s[j].x - s[i].x + (ll)abs(s[i].y - s[j].y);
            if (dis <= lim) {
                int l = s[i].id, r = s[j].id;
                if (l > r)
                    swap(l, r);
                chmx(ps[r], l);
                vec[r].emplace_back(l, dis);
            }
        }
        for (int j = i - 1; j; --j) {
            if (s[i].x - s[j].x > lim)
                break;
            ll dis = s[i].x - s[j].x + (ll)abs(s[i].y - s[j].y);
            if (dis <= lim) {
                int l = s[i].id, r = s[j].id;
                if (l > r)
                    swap(l, r);
                chmx(ps[r], l);
                vec[r].emplace_back(l, dis);
            }
        }
    }
    for (int i = 1; i <= n; ++i)
        chmx(ps[i], ps[i - 1]);
    for (int i = 1; i <= m; ++i) {
        int l = read(), r = read();
        res[i] = lINF;
        if (l > ps[r]) {
            for (int u = l; u <= r; ++u)
                for (int v = u + 1; v <= r; ++v)
                    chmn(res[i],
                         (ll)abs(px[u] - px[v]) + (ll)abs(py[u] - py[v]));
        } else
            vq[r].emplace_back(l, i);
    }
    for (int i = 1; i <= n; ++i)
        tr[i] = INF;
    for (int i = 1; i <= n; ++i) {
        for (auto [x, v] : vec[i])
            upd(x, v);
        for (auto [x, t] : vq[i])
            chmn(res[t], qry(x));
    }
    for (int i = 1; i <= m; ++i)
        printf("%lld\n", res[i]);
    return 0;
}