#include <iostream>     // Input/output stream objects
#include <fstream>      // File stream objects
#include <sstream>      // String stream objects
#include <iomanip>      // Input/output manipulators
#include <string>       // String class and functions
#include <vector>       // Dynamic array
#include <list>         // Doubly linked list
#include <set>          // Set container
#include <map>          // Map container
#include <queue>        // Queue container
#include <stack>        // Stack container
#include <algorithm>    // Algorithms on sequences (e.g., sort, find)
#include <cmath>        // Mathematical functions
#include <climits>      // LLONG_MAX, LLONG_MIN
#include <ctime>        // Date and time functions
#include <cstdlib>      // General purpose functions (e.g., memory management)
#include <cstring>      // C-style string functions
#include <cctype>       // Character classification functions
#include <cassert>      // Assert function for debugging
#include <exception>    // Standard exceptions
#include <functional>   // Function objects
#include <iterator>     // Iterator classes
#include <limits>       // Numeric limits
#include <locale>       // Localization and internationalization
#include <numeric>      // Numeric operations (e.g., accumulate)
#include <random>       // Random number generators
#include <stdexcept>    // Standard exception classes
#include <typeinfo>     // Runtime type information
#include <utility>      // Utility components (e.g., std::pair)
#include <bitset>

using namespace std;

#define FOR(i, a, b) for(int i = a; i < (b); i++)
#define FORE(i, a, b) for(int i = a; i <= (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define x first 
#define y second
#define mp make_pair
#define PI 3.141592653
#define compress(coord) sort(all(coord)), coord.resize(unique(all(coord)) - coord.begin())
const double eps = 1e-9;
const ll inf = LLONG_MAX;

static char buf[450<<20];
void* operator new(size_t s) {
    static size_t i = sizeof buf;
    assert(s < i);
    return (void*)&buf[i-=s];
}

void operator delete(void *) {}

const int INF = 1e9 + 10;

struct segData {
    int mxx, mix, mxy, miy, idmxx, idmix, idmxy, idmiy;
    segData() : mxx(-INF), mix(INF), mxy(-INF), miy(INF) {}
    segData(int mxx, int mix, int mxy, int miy, int idmxx, int idmix, int idmxy, int idmiy) : 
    mxx(mxx), mix(mix), mxy(mxy), miy(miy), idmxx(idmxx), idmix(idmix), idmxy(idmxy), idmiy(idmiy) {}
};

struct Node {
    typedef segData T;
    Node *l = 0, *r = 0;
    int lo, hi;
    T val;
    T f(T a, T b) {
        int nmxx, nmix, nmxy, nmiy;
        int nidmxx, nidmix, nidmxy, nidmiy;
        nmxx = max(a.mxx, b.mxx);
        nidmxx = a.mxx >= b.mxx ? a.idmxx : b.idmxx;

        nmix = min(a.mix, b.mix);
        nidmix = a.mix <= b.mix ? a.idmix : b.idmix;

        nmxy = max(a.mxy, b.mxy);
        nidmxy = a.mxy >= b.mxy ? a.idmxy : b.idmxy;

        nmiy = min(a.miy, b.miy);
        nidmiy = a.miy <= b.miy ? a.idmiy : b.idmiy;

        return {nmxx, nmix, nmxy, nmiy, nidmxx, nidmix, nidmxy, nidmiy};
    }

    Node (vector<pii> &v, int lo, int hi) : lo(lo), hi(hi) {
        if (lo == hi) val = T(v[lo].x, v[lo].x, v[lo].y, v[lo].y, lo, lo, lo, lo);
        else {
            int mid = lo + hi >> 1;
            l = new Node(v, lo, mid); r = new Node(v, mid + 1, hi);
            val = f(l->val, r->val);
        }
    }

    T query(int L, int R) {
        if (L > R || lo > R || hi < L) return T();
        if (lo >= L && hi <= R) return val;
        return f(l->query(L, R), r->query(L, R));
    }
};

const int N = 1e5 + 10;
int n, q;
vector<pii> pts(N);
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    cin >> n >> q;

    FORE(i, 1, n) cin >> pts[i].x >> pts[i].y;
    Node *t = new Node(pts, 1, n);
    while (q--) {
        int L, R, ans = 2*INF;
        cin >> L >> R;
        segData ret = t->query(L, R);
        segData tocal;
        tocal = t->f(t->query(L, ret.idmxx-1), t->query(ret.idmxx+1, R));
        ans = min(ans, max(tocal.mxx - tocal.mix, tocal.mxy - tocal.miy));
        
        tocal = t->f(t->query(L, ret.idmix-1), t->query(ret.idmix+1, R));
        ans = min(ans, max(tocal.mxx - tocal.mix, tocal.mxy - tocal.miy));

        tocal = t->f(t->query(L, ret.idmxy-1), t->query(ret.idmxy+1, R));
        ans = min(ans, max(tocal.mxx - tocal.mix, tocal.mxy - tocal.miy));

        tocal = t->f(t->query(L, ret.idmiy-1), t->query(ret.idmiy+1, R));
        ans = min(ans, max(tocal.mxx - tocal.mix, tocal.mxy - tocal.miy));

        cout << max(ans, 0) << endl;
    }
}