#include <iostream>
#include <vector>
#include <queue>
#define LL long long
#define pii pair<int, int>
#define ff first
#define ss second
#define MAX 5004
using namespace std;
vector<vector<int>> D;

int main() {
   std::iostream::sync_with_stdio(false);
   
    int N, Q;
    cin >> N >> Q;
    D.assign(MAX, vector<int>(MAX, -1));
    queue<pii> gua;
    for (int i = 0; i < N; ++i) {
        int a, b;
        cin >> a >> b;
        D[a][b] = 0;
        gua.push({a, b});
    }
    
    int X[] = {0,   1, 1, 1, 0, -1, -1, -1};
    int Y[] = {-1, -1, 0, 1, 1,  1,  0, -1};
    while (!gua.empty()) {
        pii cur = gua.front(); gua.pop();
        //cout << cur.ss.ff << " " << cur.ss.ss << endl;
        for (int i = 0; i < 8; ++i) {
            pii neu = {cur.ff + X[i], cur.ss + Y[i]};
            if (neu.ff >= 0 && neu.ff < MAX && neu.ss >= 0 && neu.ss < MAX && D[neu.ff][neu.ss] == -1) {
                D[neu.ff][neu.ss] = D[cur.ff][cur.ss]+ 1;
                gua.push(neu); 
            }
        }
    }
    
    for (int i = 0; i < Q; ++i) {
        int a, b;
        cin >> a >> b;
        cout << D[a][b] << endl;
    }
    return 0;
}