#include<bits/stdc++.h>

using namespace std;

bool in[5001][5001];
bool ex[5001][5001];
vector<int> ri[5001][5001];

int main() {
  int ng, ni;
	cin >> ng >> ni;
	vector<pair<int, int>> guards(ng);
	vector<int> res(ni);
	for (int i = 0; i < ng; ++i) {
                cin >> guards[i].second >> guards[i].first;
	}

	for (int i = 0; i < ni; ++i) {
		int ix, iy;
		cin >> ix >> iy;
		in[iy][ix] = true;
		ri[iy][ix].push_back(i);
	}

	int rounds = 0;
	for (;;) {
		vector<pair<int,int>> new_g;
		for (auto& p : guards) {
			if (ex[p.first][p.second]) {
				continue;
			}
			ex[p.first][p.second] = true;
			if (in[p.first][p.second]) {
				for (int riv: ri[p.first][p.second]) {
					res[riv] = rounds;
				}
			}
			for (int y = -1; y <= 1; ++y) {
				for (int x = -1; x <= 1; ++x) {
					if (p.first + y >= 0 && p.first + y <= 5000 && p.second + x >= 0
 						&& p.second + x < 5001 && !ex[p.first + y][p.second + x])
						{
							new_g.emplace_back(p.first + y, p.second + x);
						}
				}
			}
		}
		++rounds;
		swap(guards, new_g);
		if (guards.empty()) {
			break;
		} 	
	}
	for (int a : res) {
		cout << a << endl;
	}
  return 0;
}