#include <bits/stdc++.h>

#define REP(i, n) for(int (i)=0;(i)<(n);(i)++)

using namespace std;

#define ull unsigned long long

pair<int, int> pos[1000000];
pair<int, int> sec[1000000];

queue< pair<int, int> > q;

int times[5001][5001];

int n,m;

void go(int x, int y, int t){
    if (x < 0 || y<0 || x > 5000 || y > 5000) return;
    if (times[x][y] <= t) return;
    times[x][y] = t;
    q.push({x,y});
}

int main(){
    cin >> n >> m;
    REP(i, n) {
        cin >> sec[i].first >> sec[i].second;
    }
    REP(i, m) {
        cin >> pos[i].first >> pos[i].second;
    }

    REP(i, 5001) REP(j, 5001) times[i][j] = 100000;

    REP(i, n) {
        q.push(sec[i]);
        times[sec[i].first][sec[i].second] = 0;
    }

    while(q.size()){
        auto p = q.front();
        q.pop();
        int t = times[p.first][p.second] + 1;
        for (int i=-1;i<2;i++){
            for (int j=-1;j<2;j++){
                go(p.first+i, p.second+j, t);
            }
        }
    }

//    REP(i,10){
//        cout << endl;
//        REP(j, 10){
//            cout << times[i][j] << " ";
//        }
//    }

    REP(i, m) {
        cout << times[pos[i].first][pos[i].second] << endl;
    }

}