#include <bits/stdc++.h>
#define el "\n"
#define sp " "
#define fi first
#define se second
#define inf 1e18
#define r0 return 0
#define int long long
#define F(i, a, b, c) for (int i = a; i <= b; i += c)
#define debug puts("Yuexingfei_qwq")
#define TheEnd continue
#define p 1000000007

using namespace std;

typedef long long ll;
typedef string str;
using ull = unsigned ll;

const int d1[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
int n, m;
int d[5100][5100];
int a[310000][2];
struct Info {
	int x, y;
} q[25010010];

inline void out(int n, int m) {
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			cout << d[i][j] << sp;
		}
		cout << el;
	}
	cout << el;
}

inline void bfs(void) {
	for (int i = 0; i <= 5001; i++) {
		for (int j = 0; j <= 5001; j++) {
			d[i][j] = -1;
		}
	}
	int front = 1, rear = 0;
	for (int i = 1; i <= n; i++) {
		d[a[i][0]][a[i][1]] = 0;
		q[++rear].x = a[i][0], q[rear].y = a[i][1];
	}
	while (front <= rear) {
		int x = q[front].x, y = q[front++].y;
		for (int i = 0; i < 8; i++) {
			int xx = x + d1[i][0], yy = y + d1[i][1];
			if (xx < 0 || xx > 5000 || yy < 0 || yy > 5000) {
				continue;
			}
			if (d[xx][yy] == -1) {
				d[xx][yy] = d[x][y] + 1;
				q[++rear].x = xx, q[rear].y = yy;
			}
		}
	}
}

signed main(void) {
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i][0] >> a[i][1];
	}
	bfs();
	while (m--) {
		int x, y;
		cin >> x >> y;
		cout << d[x][y] << el;
	}
	return 0;
}

老师说bfs的初始化出问题了，但是这个大聪明看不出来、、、