#include <bits/stdc++.h>

using namespace std;

array<array<int, 5001>, 5001> net;

int main()
{
    for (auto &item : net)
        item.fill(10000);

    int N, Q, X, Y;
    cin >> N >> Q;
    queue<pair<int, int> > q;
    for (int i = 0; i < N; ++i)
    {
        cin >> X >> Y;
        net[X][Y] = 0;
        q.push({X, Y});
    }

    while (!q.empty())
    {
        auto item = q.front();
        q.pop();
        int value = net[item.first][item.second];
        for (int i = -1; i < 2; ++i)
        {
            for (int j = -1; j < 2; ++j)
            {
                if (i == 0 && j == 0) continue;
                if (item.first + i < 0 || item.first + i > 5000) continue;
                if (item.second + j < 0 || item.second + j > 5000) continue;
                if (net[item.first + i][item.second + j] > value + 1)
                {
                    net[item.first + i][item.second + j] = value + 1;
                    q.push({item.first + i, item.second + j});
                }
            }
        }
    }

    for (int i = 0; i < Q; ++i)
    {
        cin >> X >> Y;
        cout << net[X][Y] << '\n';
    }

    return 0;
}