#include<bits/stdc++.h>
#include <iomanip>
using namespace std;
#define EPS (1e-10)
#define REP(i,n) for (int i =0; i < (n);i++)


typedef long double ld;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<double,double> pdd;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<vector<int> > vvi;
typedef vector<ii> vii;

/*
 * 
 */

int safe_ask(int x, int y, vvi &pref) {
    x = max(x, 0);
    y = max(y, 0);
    x = min(x, 5002);
    y = min(y, 5002);
    return pref[x][y];
}

int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    int N, Q; cin >> N >> Q;
    vi sx(Q), sy(Q);
    vvi pref(5003, vi(5003, 0));
    
    int x, y;
    REP(i, N) {
        cin >> x >> y;
        ++y; ++x;
        pref[x][y]++;
    }
    
    for(int i = 1; i < 5003; ++i) {
        for(int j = 1; j < 5003; ++j) {
            pref[i][j] += pref[i][j-1] + pref[i-1][j] - pref[i-1][j-1];
        }
    }
        
    REP(i, Q) {
        cin >> x >> y;
        ++x; ++y;
        int a = 0, b = 5002;
        int res = INT_MAX;
        while(a <= b) {
            int m = (a+b)/2;
//            cout << m << " " << safe_ask(x+m, y+m, pref) + safe_ask(x-m-1, y-m-1, pref) - 
//                    safe_ask(x-m-1, y+m, pref) - safe_ask(x+m, y-m-1, pref) << endl;
            if (safe_ask(x+m, y+m, pref) + safe_ask(x-m-1, y-m-1, pref) - 
                    safe_ask(x-m-1, y+m, pref) - safe_ask(x+m, y-m-1, pref)) {
                res = min(res, m);
                b = m-1;
            } else {
                a = m+1;
            }
        }
//        if (safe_ask(x+a, y+a, pref) + safe_ask(x-a-1, y-a-1, pref) - 
//                    safe_ask(x-a-1, y+a, pref) - safe_ask(x+a, y-a-1, pref)) {
//                res = min(res, a);
//                
//        }
//                if (safe_ask(x+b, y+b, pref) + safe_ask(x-b-1, y-b-1, pref) - 
//                    safe_ask(x-b-1, y+b, pref) - safe_ask(x+b, y-b-1, pref)) {
//                res = min(res, b);
//                
//        }
        cout << res << endl;
    }
        
    return 0;
}