#include <bits/stdc++.h>

using namespace std;

const int MAX_DIM = 5001;

int n, q;
int plane[MAX_DIM][MAX_DIM]; // -2 nowhere, -1 in next level, <0, inf> done

void init() {
    for (int r = 0; r < MAX_DIM; ++r)
        for (int c = 0; c < MAX_DIM; ++c)
            plane[r][c] = -2;
}

inline bool ok_point(int x, int y) {
    return 0 <= x && x < MAX_DIM && 0 <= y && y < MAX_DIM;
}

int main() {
    init();
    cin >> n >> q;

    int level = 0;
    vector<pair<int, int>> now_level;
    vector<pair<int, int>> next_level;
    
    // get all policemen
    for (int i = 0; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        now_level.emplace_back(x, y);
    }

    while (!now_level.empty()) {
        // update
        for (const auto& pt : now_level)
            plane[pt.first][pt.second] = level;
        // look around, fill next level
        static const vector<pair<int, int>> moves = {{-1, -1}, {-1, 0}, {-1, +1}, {0, +1}, {+1, +1}, {+1, 0}, {+1, -1}, {0, -1}};
        for (const auto& pt : now_level)
            for (const auto& mv : moves) {
	    	int x = pt.first + mv.first;
		int y = pt.second + mv.second;

		if (ok_point(x, y) && plane[x][y] == -2)
	            next_level.emplace_back(x, y),
                    plane[x][y] = -1;
	    }

        now_level.clear();
        swap(now_level, next_level);
        level++;
    }
    
    // answer all queries
    for (int i = 0; i < q; ++i) {
        int x, y;
        cin >> x >> y;
        cout << plane[x][y] << '\n';
    }
}