#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() {
    int N, Q;
    cin >> N >> Q;
    D.assign(MAX, vector<int>(MAX, -1));
    queue<pair<int, pii>> gua;
    for (int i = 0; i < N; ++i) {
        int a, b;
        cin >> a >> b;
        gua.push({0, {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()) {
        pair<int, pii> cur = gua.front(); gua.pop();
        if (D[cur.ss.ff][cur.ss.ss] != -1) 
            continue;
        D[cur.ss.ff][cur.ss.ss] = cur.ff;
        //cout << cur.ss.ff << " " << cur.ss.ss << endl;
        for (int i = 0; i < 8; ++i) {
            pii neu = {cur.ss.ff + X[i], cur.ss.ss + Y[i]};
            if (neu.ff >= 0 && neu.ff <= 5000 && neu.ss >= 0 && neu.ss <= 500) {
                gua.push({cur.ff + 1, {neu}}); 
            }
        }
    }
    
    for (int i = 0; i < Q; ++i) {
        int a, b;
        cin >> a >> b;
        cout << D[a][b] << endl;
    }
    return 0;
}